docs/optable.pod

   1 # Copyright (C) 2005-2007, Parrot Foundation.
   2 # $Id$
   3
   4 =head1 ***** WARNING *****
   5
   6 This is an ALPHA pod! The contents herein may not reflect reality. :)
   7
   8 =head1 NAME
   9
  10 docs/optable.pod - PGE operator precedence table and parser
  11
  12 =head1 VERSION
  13
  14 $Revision$
  15
  16 =head1 DESCRIPTION
  17
  18 PGE::OPTable is the bottom up shift/reduce style parser component of the
  19 Parrot Grammar Engine (PGE) suite. PGE is a Parrot implementation of Perl6
  20 rules.
  21
  22 =head1 FUTURE CONSIDERATIONS
  23
  24 =over 4
  25
  26 =item - Shift reduce application to more general grammar productions than just
  27 operators.
  28
  29 =item - Static state machine transition table generation.  (Optimization)
  30
  31 =item - tighter and looser should work even when their argument operator
  32 hasn't been defined yet.
  33
  34 =back
  35
  36 =head1 DEFINITIONS
  37
  38 =head2 "operator"
  39
  40 An operator is a most often mathematical function usually taking one or two
  41 arguments (operands, also called terms) and returning a calculated result.
  42 Operators are often characterized as pure (no side effects).  Obvious
  43 exceptions to this rule are increment (++) and decrement (--) operators and
  44 assignment operators such as +=, *=, etc.
  45
  46 Operators which have one operand are called unary operators.  Unary operator
  47 symbols may appear in the prefix position (in front of the term) or in the
  48 postfix position (following the term).  Binary operators have two operators.
  49 Binary operator symbols usually appear in the infix position between the two
  50 operands. Ternary operators also exist, such as the C style ternary
  51 conditional operator C< expression ? true case : false case>. See Synopsis 5
  52 Rules for more information.
  53
  54 =head2 "expression"
  55
  56 An expression is a combination of operators, operands (terms such as variables
  57 and values) and grouping symbols that describe a computation.  Expressions
  58 return a result.
  59
  60 =head2 "term"
  61
  62 A term is the atomic unit on which an operator operates.  Operand is the more
  63 formal mathematical term for term. :) In OPTable parsed expressions a term is
  64 a variable or primitive value.
  65
  66 =head2 "precedence"
  67
  68 Precedence is the order in which operators are evaluated.  Higher precedence
  69 operators are evaluated before lower precedence operators.
  70
  71 =head2 "precedence level"
  72
  73 Computer languages usually have a table of operator precedences.  Operators at
  74 the top of the table have higher precedence than those below.  Operators at
  75 the same vertical level in the table have equivalent or equal precedence.  An
  76 operator's level in the table is called its precedence level.  OPTable uses
  77 integers to signify precedence.  The greater the OPTable precedence integer
  78 the higher the precedence level of the operator.  An operator with precedence
  79 level 22 has higher precedence that an operator with precedence level 5 and
  80 will be evaluated first.
  81
  82 =head2 "shift/reduce"
  83
  84 TODO
  85
  86 =head1 SYNTAX
  87
  88   grammar NAMESPACE;
  89
  90   proto OPERATOR_NAME ADVERBIAL_CLAUSES* { ... }
  91
  92 The C<grammar> statement at the top is the namespace in which the optable
  93 will be generated.  Written in Perl6 style the C<grammar> statement is
  94 translated by PGE into valid Parrot namespace syntax.
  95
  96 The C<proto> statement declares an operator to be added to the precedence table
  97 and parser.  All operator attributes are defined using the Perl6 adverbial
  98 style of C<is ADVERB()>.  Adverbial clauses are separated by white space.
  99 Adverbs can have 0-arity in which case they can be written without
 100 parentheses.  Adverbial arguments are written comma separated in parentheses.
 101
 102 =head2 "Adverbial Precedence Clauses"
 103
 104 =over 4
 105
 106 =item - is precedence(PRECEDENCE_LEVEL_STRING)
 107
 108 C<is precedence> takes a single string argument which contains the precedence
 109 level for the current operator that C<is precedence> is modifying.  The C<is
 110 precedence> argument string is formatted as a integer precedence level
 111 followed by equals sign. e.g. '22='
 112
 113 =item - is tighter(PREVIOUSLY_DEFINED_OPERATOR_NAME)
 114
 115 C<is tighter> takes a B<previously> defined operator name as its single
 116 argument.  The argument operator's precedence level plus 1 is then used as the
 117 precedence level for the current operator that C<is tighter> is modifying.
 118
 119 =item - is looser(PREVIOUSLY_DEFINED_OPERATOR_NAME)
 120
 121 C<is looser> takes a B<previously> defined operator name as its single
 122 argument.  The argument operator's precedence level minus 1 is then used as
 123 the precedence level for the current operator that C<is looser> is modifying.
 124
 125 =item - is equiv(PREVIOUSLY_DEFINED_OPERATOR_NAME)
 126
 127 C<is equiv> takes a B<previously> defined operator name as its single
 128 argument.  The argument operator's precedence level is used as the precedence
 129 level for the current operator that C<is equiv> is modifying.
 130
 131 =item - is assoc(DESCRIPTION)
 132
 133 DESCRIPTION can be one of 'list', 'left', 'right', 'non', or 'chain'.
 134
 135 C<is assoc> declares the associativity of the operator.  The absence of a C<is
 136 assoc> adverb indicates that the operation is associative or that the order of
 137 evaluation of two or more instances of an operator in an expression is
 138 unimportant.  C<'left'> signifies left association; evaluation should occur
 139 from the left.  Conversely, C<'right'> signifies right association; evaluation
 140 should occur from the right.  C<'non'> declares that this operator doesn't
 141 strongly associate to the left or right.  C<'list'> specifies that the
 142 operator is associated as a list context.  C<'chain'> declares chained
 143 association such as C<a = b = c = 10> or C< a < 10 < b>.
 144
 145
 146 =back
 147
 148 =head2 "Adverbial Clauses"
 149
 150 =over 4
 151
 152 =item - is parsed()
 153
 154 PGE::OPTable normally generates the parsing code for an operator based on the
 155 operator name which usually consists of the operator's orientation followed by
 156 a colon and then the operator symbol. In Perl6 'infix:*' is an example
 157 operator name of the infix multiplication operator.  'infix:x' likewise
 158 represents the Perl6 repeat operator.  The C<is parsed> adverb declares that
 159 this particular operator is parsed using the Perl6 match conforming method
 160 specified as the adverbs argument instead of auto-generated code based off of
 161 the operator's name.
 162
 163 =item - is pastrule()
 164
 165 The C<is pastrule> adverb defines the pastrule attribute of an operator.
 166 During later processing by the Tree Grammar Engine (TGE) compiler tool, the
 167 pastrule attribute can be used to specify custom TGE processing.
 168
 169 TODO: needs concrete example
 170
 171 =item - is post()
 172
 173 The C<is post> adverb specifies the Parrot opcode that implements the
 174 semantics of this particular operator. C<is post('add')> is used to annotate
 175 the 'infix:+' operator in languages where the infix + symbol denotes addition.
 176
 177 =item - is expect()
 178
 179 The C<is expect> adverb used to specify the hexadecimal identifier of the next
 180 token OPTable should expect???
 181
 182 =item - is returns()
 183
 184 The C<is returns> adverb specifies the type of the result for this operator.
 185 TGE can use this attribute to construct correctly typed temporary to hold the
 186 intermediate results of operations for later use or combination.
 187
 188 =item - is pir()
 189
 190 The C<is pir> adverb specifies a code generation emit string that can be used
 191 during code generation.  Parrot assembly is emitted as Parrot Intermediate
 192 Representation (PIR).  Hence the adverb name pir. The argument string is a
 193 format string, after the C style printf format string. C<%r> represents the
 194 result of the operation.  C<%0>, C<%1>, etc represent the operands of the
 195 operator.  proto 'infix:~&' is equiv('infix:*') is pir(" %r = bands %0, %1") {
 196 ... }
 197
 198
 199 =item - is nullterm
 200
 201 The C<is nullterm> adverb specifies that the operator is an 0-arity function
 202 that doesn't take any operands.
 203
 204 =item - is stop()
 205 TODO: needs help, stolen shamelessly from compilers/pge/PGE/OPTable.pir
 206
 207 The C<is stop> adverb declares a string to be matched directly or a sub(rule)
 208 to be called to check for a match.
 209
 210 =back
 211
 212 =head1 IMPLEMENTATION
 213
 214 TODO: how it works inside :)
 215
 216 =head1 LANGUAGE NOTES
 217
 218 None.
 219
 220 =head1 EXAMPLES
 221
 222   languages/perl6/src/grammar_optok.pg
 223   languages/cardinal/src/cardinal_optok.pg
 224
 225 =head1 ATTACHMENTS
 226
 227 None.
 228
 229 =head1 FOOTNOTES
 230
 231 None.
 232
 233 =head1 REFERENCES
 234
 235   http://en.wikipedia.org/wiki/Order_of_operations
 236   http://en.wikipedia.org/wiki/Associativity
 237   http://en.wikipedia.org/wiki/Bottom-up_parsing
 238   http://www.ozonehouse.com/mark/blog/code/PeriodicTable.html
 239   http://dev.perl.org/perl6/doc/design/syn/S03.html
 240
 241   compilers/tge
 242   compilers/past
 243   languages/perl6/src/PAST.pir
 244   languages/perl6/src/POST.pir
 245
 246 =cut
 247
 248 __END__
 249 Local Variables:
 250   fill-column:78
 251 End: