| OLD | NEW |
|---|
| 1 <html> | 1 <html> |
| 2 <head> | 2 <head> |
| 3 <title>The Lemon Parser Generator</title> | 3 <title>The Lemon Parser Generator</title> |
| 4 </head> | 4 </head> |
| 5 <body bgcolor=white> | 5 <body bgcolor=white> |
| 6 <h1 align=center>The Lemon Parser Generator</h1> | 6 <h1 align=center>The Lemon Parser Generator</h1> |
| 7 | 7 |
| 8 <p>Lemon is an LALR(1) parser generator for C or C++. | 8 <p>Lemon is an LALR(1) parser generator for C. |
| 9 It does the same job as ``bison'' and ``yacc''. | 9 It does the same job as "bison" and "yacc". |
| 10 But lemon is not another bison or yacc clone. It | 10 But lemon is not a bison or yacc clone. Lemon |
| 11 uses a different grammar syntax which is designed to | 11 uses a different grammar syntax which is designed to |
| 12 reduce the number of coding errors. Lemon also uses a more | 12 reduce the number of coding errors. Lemon also uses a |
| 13 sophisticated parsing engine that is faster than yacc and | 13 parsing engine that is faster than yacc and |
| 14 bison and which is both reentrant and thread-safe. | 14 bison and which is both reentrant and threadsafe. |
| 15 Furthermore, Lemon implements features that can be used | 15 (Update: Since the previous sentence was written, bison |
| 16 has also been updated so that it too can generate a |
| 17 reentrant and threadsafe parser.) |
| 18 Lemon also implements features that can be used |
| 16 to eliminate resource leaks, making is suitable for use | 19 to eliminate resource leaks, making is suitable for use |
| 17 in long-running programs such as graphical user interfaces | 20 in long-running programs such as graphical user interfaces |
| 18 or embedded controllers.</p> | 21 or embedded controllers.</p> |
| 19 | 22 |
| 20 <p>This document is an introduction to the Lemon | 23 <p>This document is an introduction to the Lemon |
| 21 parser generator.</p> | 24 parser generator.</p> |
| 22 | 25 |
| 23 <h2>Theory of Operation</h2> | 26 <h2>Theory of Operation</h2> |
| 24 | 27 |
| 25 <p>The main goal of Lemon is to translate a context free grammar (CFG) | 28 <p>The main goal of Lemon is to translate a context free grammar (CFG) |
| (...skipping 11 matching lines...) Expand all Loading... |
| 37 | 40 |
| 38 <p>Depending on command-line options, Lemon will generate between | 41 <p>Depending on command-line options, Lemon will generate between |
| 39 one and three files of outputs. | 42 one and three files of outputs. |
| 40 <ul> | 43 <ul> |
| 41 <li>C code to implement the parser. | 44 <li>C code to implement the parser. |
| 42 <li>A header file defining an integer ID for each terminal symbol. | 45 <li>A header file defining an integer ID for each terminal symbol. |
| 43 <li>An information file that describes the states of the generated parser | 46 <li>An information file that describes the states of the generated parser |
| 44 automaton. | 47 automaton. |
| 45 </ul> | 48 </ul> |
| 46 By default, all three of these output files are generated. | 49 By default, all three of these output files are generated. |
| 47 The header file is suppressed if the ``-m'' command-line option is | 50 The header file is suppressed if the "-m" command-line option is |
| 48 used and the report file is omitted when ``-q'' is selected.</p> | 51 used and the report file is omitted when "-q" is selected.</p> |
| 49 | 52 |
| 50 <p>The grammar specification file uses a ``.y'' suffix, by convention. | 53 <p>The grammar specification file uses a ".y" suffix, by convention. |
| 51 In the examples used in this document, we'll assume the name of the | 54 In the examples used in this document, we'll assume the name of the |
| 52 grammar file is ``gram.y''. A typical use of Lemon would be the | 55 grammar file is "gram.y". A typical use of Lemon would be the |
| 53 following command: | 56 following command: |
| 54 <pre> | 57 <pre> |
| 55 lemon gram.y | 58 lemon gram.y |
| 56 </pre> | 59 </pre> |
| 57 This command will generate three output files named ``gram.c'', | 60 This command will generate three output files named "gram.c", |
| 58 ``gram.h'' and ``gram.out''. | 61 "gram.h" and "gram.out". |
| 59 The first is C code to implement the parser. The second | 62 The first is C code to implement the parser. The second |
| 60 is the header file that defines numerical values for all | 63 is the header file that defines numerical values for all |
| 61 terminal symbols, and the last is the report that explains | 64 terminal symbols, and the last is the report that explains |
| 62 the states used by the parser automaton.</p> | 65 the states used by the parser automaton.</p> |
| 63 | 66 |
| 64 <h3>Command Line Options</h3> | 67 <h3>Command Line Options</h3> |
| 65 | 68 |
| 66 <p>The behavior of Lemon can be modified using command-line options. | 69 <p>The behavior of Lemon can be modified using command-line options. |
| 67 You can obtain a list of the available command-line options together | 70 You can obtain a list of the available command-line options together |
| 68 with a brief explanation of what each does by typing | 71 with a brief explanation of what each does by typing |
| 69 <pre> | 72 <pre> |
| 70 lemon -? | 73 lemon -? |
| 71 </pre> | 74 </pre> |
| 72 As of this writing, the following command-line options are supported: | 75 As of this writing, the following command-line options are supported: |
| 73 <ul> | 76 <ul> |
| 74 <li><tt>-b</tt> | 77 <li><b>-b</b> |
| 75 <li><tt>-c</tt> | 78 Show only the basis for each parser state in the report file. |
| 76 <li><tt>-g</tt> | 79 <li><b>-c</b> |
| 77 <li><tt>-m</tt> | 80 Do not compress the generated action tables. |
| 78 <li><tt>-q</tt> | 81 <li><b>-D<i>name</i></b> |
| 79 <li><tt>-s</tt> | 82 Define C preprocessor macro <i>name</i>. This macro is useable by |
| 80 <li><tt>-x</tt> | 83 "%ifdef" lines in the grammar file. |
| 84 <li><b>-g</b> |
| 85 Do not generate a parser. Instead write the input grammar to standard |
| 86 output with all comments, actions, and other extraneous text removed. |
| 87 <li><b>-l</b> |
| 88 Omit "#line" directives in the generated parser C code. |
| 89 <li><b>-m</b> |
| 90 Cause the output C source code to be compatible with the "makeheaders" |
| 91 program. |
| 92 <li><b>-p</b> |
| 93 Display all conflicts that are resolved by |
| 94 <a href='#precrules'>precedence rules</a>. |
| 95 <li><b>-q</b> |
| 96 Suppress generation of the report file. |
| 97 <li><b>-r</b> |
| 98 Do not sort or renumber the parser states as part of optimization. |
| 99 <li><b>-s</b> |
| 100 Show parser statistics before existing. |
| 101 <li><b>-T<i>file</i></b> |
| 102 Use <i>file</i> as the template for the generated C-code parser implementation. |
| 103 <li><b>-x</b> |
| 104 Print the Lemon version number. |
| 81 </ul> | 105 </ul> |
| 82 The ``-b'' option reduces the amount of text in the report file by | |
| 83 printing only the basis of each parser state, rather than the full | |
| 84 configuration. | |
| 85 The ``-c'' option suppresses action table compression. Using -c | |
| 86 will make the parser a little larger and slower but it will detect | |
| 87 syntax errors sooner. | |
| 88 The ``-g'' option causes no output files to be generated at all. | |
| 89 Instead, the input grammar file is printed on standard output but | |
| 90 with all comments, actions and other extraneous text deleted. This | |
| 91 is a useful way to get a quick summary of a grammar. | |
| 92 The ``-m'' option causes the output C source file to be compatible | |
| 93 with the ``makeheaders'' program. | |
| 94 Makeheaders is a program that automatically generates header files | |
| 95 from C source code. When the ``-m'' option is used, the header | |
| 96 file is not output since the makeheaders program will take care | |
| 97 of generated all header files automatically. | |
| 98 The ``-q'' option suppresses the report file. | |
| 99 Using ``-s'' causes a brief summary of parser statistics to be | |
| 100 printed. Like this: | |
| 101 <pre> | |
| 102 Parser statistics: 74 terminals, 70 nonterminals, 179 rules | |
| 103 340 states, 2026 parser table entries, 0 conflicts | |
| 104 </pre> | |
| 105 Finally, the ``-x'' option causes Lemon to print its version number | |
| 106 and then stops without attempting to read the grammar or generate a parser.</p> | |
| 107 | 106 |
| 108 <h3>The Parser Interface</h3> | 107 <h3>The Parser Interface</h3> |
| 109 | 108 |
| 110 <p>Lemon doesn't generate a complete, working program. It only generates | 109 <p>Lemon doesn't generate a complete, working program. It only generates |
| 111 a few subroutines that implement a parser. This section describes | 110 a few subroutines that implement a parser. This section describes |
| 112 the interface to those subroutines. It is up to the programmer to | 111 the interface to those subroutines. It is up to the programmer to |
| 113 call these subroutines in an appropriate way in order to produce a | 112 call these subroutines in an appropriate way in order to produce a |
| 114 complete system.</p> | 113 complete system.</p> |
| 115 | 114 |
| 116 <p>Before a program begins using a Lemon-generated parser, the program | 115 <p>Before a program begins using a Lemon-generated parser, the program |
| 117 must first create the parser. | 116 must first create the parser. |
| 118 A new parser is created as follows: | 117 A new parser is created as follows: |
| 119 <pre> | 118 <pre> |
| 120 void *pParser = ParseAlloc( malloc ); | 119 void *pParser = ParseAlloc( malloc ); |
| 121 </pre> | 120 </pre> |
| 122 The ParseAlloc() routine allocates and initializes a new parser and | 121 The ParseAlloc() routine allocates and initializes a new parser and |
| 123 returns a pointer to it. | 122 returns a pointer to it. |
| 124 The actual data structure used to represent a parser is opaque -- | 123 The actual data structure used to represent a parser is opaque — |
| 125 its internal structure is not visible or usable by the calling routine. | 124 its internal structure is not visible or usable by the calling routine. |
| 126 For this reason, the ParseAlloc() routine returns a pointer to void | 125 For this reason, the ParseAlloc() routine returns a pointer to void |
| 127 rather than a pointer to some particular structure. | 126 rather than a pointer to some particular structure. |
| 128 The sole argument to the ParseAlloc() routine is a pointer to the | 127 The sole argument to the ParseAlloc() routine is a pointer to the |
| 129 subroutine used to allocate memory. Typically this means ``malloc()''.</p> | 128 subroutine used to allocate memory. Typically this means malloc().</p> |
| 130 | 129 |
| 131 <p>After a program is finished using a parser, it can reclaim all | 130 <p>After a program is finished using a parser, it can reclaim all |
| 132 memory allocated by that parser by calling | 131 memory allocated by that parser by calling |
| 133 <pre> | 132 <pre> |
| 134 ParseFree(pParser, free); | 133 ParseFree(pParser, free); |
| 135 </pre> | 134 </pre> |
| 136 The first argument is the same pointer returned by ParseAlloc(). The | 135 The first argument is the same pointer returned by ParseAlloc(). The |
| 137 second argument is a pointer to the function used to release bulk | 136 second argument is a pointer to the function used to release bulk |
| 138 memory back to the system.</p> | 137 memory back to the system.</p> |
| 139 | 138 |
| 140 <p>After a parser has been allocated using ParseAlloc(), the programmer | 139 <p>After a parser has been allocated using ParseAlloc(), the programmer |
| 141 must supply the parser with a sequence of tokens (terminal symbols) to | 140 must supply the parser with a sequence of tokens (terminal symbols) to |
| 142 be parsed. This is accomplished by calling the following function | 141 be parsed. This is accomplished by calling the following function |
| 143 once for each token: | 142 once for each token: |
| 144 <pre> | 143 <pre> |
| 145 Parse(pParser, hTokenID, sTokenData, pArg); | 144 Parse(pParser, hTokenID, sTokenData, pArg); |
| 146 </pre> | 145 </pre> |
| 147 The first argument to the Parse() routine is the pointer returned by | 146 The first argument to the Parse() routine is the pointer returned by |
| 148 ParseAlloc(). | 147 ParseAlloc(). |
| 149 The second argument is a small positive integer that tells the parse the | 148 The second argument is a small positive integer that tells the parse the |
| 150 type of the next token in the data stream. | 149 type of the next token in the data stream. |
| 151 There is one token type for each terminal symbol in the grammar. | 150 There is one token type for each terminal symbol in the grammar. |
| 152 The gram.h file generated by Lemon contains #define statements that | 151 The gram.h file generated by Lemon contains #define statements that |
| 153 map symbolic terminal symbol names into appropriate integer values. | 152 map symbolic terminal symbol names into appropriate integer values. |
| 154 (A value of 0 for the second argument is a special flag to the | 153 A value of 0 for the second argument is a special flag to the |
| 155 parser to indicate that the end of input has been reached.) | 154 parser to indicate that the end of input has been reached. |
| 156 The third argument is the value of the given token. By default, | 155 The third argument is the value of the given token. By default, |
| 157 the type of the third argument is integer, but the grammar will | 156 the type of the third argument is integer, but the grammar will |
| 158 usually redefine this type to be some kind of structure. | 157 usually redefine this type to be some kind of structure. |
| 159 Typically the second argument will be a broad category of tokens | 158 Typically the second argument will be a broad category of tokens |
| 160 such as ``identifier'' or ``number'' and the third argument will | 159 such as "identifier" or "number" and the third argument will |
| 161 be the name of the identifier or the value of the number.</p> | 160 be the name of the identifier or the value of the number.</p> |
| 162 | 161 |
| 163 <p>The Parse() function may have either three or four arguments, | 162 <p>The Parse() function may have either three or four arguments, |
| 164 depending on the grammar. If the grammar specification file request | 163 depending on the grammar. If the grammar specification file requests |
| 165 it, the Parse() function will have a fourth parameter that can be | 164 it (via the <a href='#extraarg'><tt>extra_argument</tt> directive</a>), |
| 165 the Parse() function will have a fourth parameter that can be |
| 166 of any type chosen by the programmer. The parser doesn't do anything | 166 of any type chosen by the programmer. The parser doesn't do anything |
| 167 with this argument except to pass it through to action routines. | 167 with this argument except to pass it through to action routines. |
| 168 This is a convenient mechanism for passing state information down | 168 This is a convenient mechanism for passing state information down |
| 169 to the action routines without having to use global variables.</p> | 169 to the action routines without having to use global variables.</p> |
| 170 | 170 |
| 171 <p>A typical use of a Lemon parser might look something like the | 171 <p>A typical use of a Lemon parser might look something like the |
| 172 following: | 172 following: |
| 173 <pre> | 173 <pre> |
| 174 01 ParseTree *ParseFile(const char *zFilename){ | 174 01 ParseTree *ParseFile(const char *zFilename){ |
| 175 02 Tokenizer *pTokenizer; | 175 02 Tokenizer *pTokenizer; |
| 176 03 void *pParser; | 176 03 void *pParser; |
| 177 04 Token sToken; | 177 04 Token sToken; |
| 178 05 int hTokenId; | 178 05 int hTokenId; |
| 179 06 ParserState sState; | 179 06 ParserState sState; |
| 180 07 | 180 07 |
| 181 08 pTokenizer = TokenizerCreate(zFilename); | 181 08 pTokenizer = TokenizerCreate(zFilename); |
| 182 09 pParser = ParseAlloc( malloc ); | 182 09 pParser = ParseAlloc( malloc ); |
| 183 10 InitParserState(&sState); | 183 10 InitParserState(&sState); |
| 184 11 while( GetNextToken(pTokenizer, &hTokenId, &sToken) ){ | 184 11 while( GetNextToken(pTokenizer, &hTokenId, &sToken) ){ |
| 185 12 Parse(pParser, hTokenId, sToken, &sState); | 185 12 Parse(pParser, hTokenId, sToken, &sState); |
| 186 13 } | 186 13 } |
| 187 14 Parse(pParser, 0, sToken, &sState); | 187 14 Parse(pParser, 0, sToken, &sState); |
| 188 15 ParseFree(pParser, free ); | 188 15 ParseFree(pParser, free ); |
| 189 16 TokenizerFree(pTokenizer); | 189 16 TokenizerFree(pTokenizer); |
| 190 17 return sState.treeRoot; | 190 17 return sState.treeRoot; |
| 191 18 } | 191 18 } |
| 192 </pre> | 192 </pre> |
| 193 This example shows a user-written routine that parses a file of | 193 This example shows a user-written routine that parses a file of |
| 194 text and returns a pointer to the parse tree. | 194 text and returns a pointer to the parse tree. |
| 195 (We've omitted all error-handling from this example to keep it | 195 (All error-handling code is omitted from this example to keep it |
| 196 simple.) | 196 simple.) |
| 197 We assume the existence of some kind of tokenizer which is created | 197 We assume the existence of some kind of tokenizer which is created |
| 198 using TokenizerCreate() on line 8 and deleted by TokenizerFree() | 198 using TokenizerCreate() on line 8 and deleted by TokenizerFree() |
| 199 on line 16. The GetNextToken() function on line 11 retrieves the | 199 on line 16. The GetNextToken() function on line 11 retrieves the |
| 200 next token from the input file and puts its type in the | 200 next token from the input file and puts its type in the |
| 201 integer variable hTokenId. The sToken variable is assumed to be | 201 integer variable hTokenId. The sToken variable is assumed to be |
| 202 some kind of structure that contains details about each token, | 202 some kind of structure that contains details about each token, |
| 203 such as its complete text, what line it occurs on, etc. </p> | 203 such as its complete text, what line it occurs on, etc. </p> |
| 204 | 204 |
| 205 <p>This example also assumes the existence of structure of type | 205 <p>This example also assumes the existence of structure of type |
| (...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 256 <li>Lemon uses no global variables. Yacc and bison use global variables | 256 <li>Lemon uses no global variables. Yacc and bison use global variables |
| 257 to pass information between the tokenizer and parser. | 257 to pass information between the tokenizer and parser. |
| 258 <li>Lemon allows multiple parsers to be running simultaneously. Yacc | 258 <li>Lemon allows multiple parsers to be running simultaneously. Yacc |
| 259 and bison do not. | 259 and bison do not. |
| 260 </ul> | 260 </ul> |
| 261 These differences may cause some initial confusion for programmers | 261 These differences may cause some initial confusion for programmers |
| 262 with prior yacc and bison experience. | 262 with prior yacc and bison experience. |
| 263 But after years of experience using Lemon, I firmly | 263 But after years of experience using Lemon, I firmly |
| 264 believe that the Lemon way of doing things is better.</p> | 264 believe that the Lemon way of doing things is better.</p> |
| 265 | 265 |
| 266 <p><i>Updated as of 2016-02-16:</i> |
| 267 The text above was written in the 1990s. |
| 268 We are told that Bison has lately been enhanced to support the |
| 269 tokenizer-calls-parser paradigm used by Lemon, and to obviate the |
| 270 need for global variables.</p> |
| 271 |
| 266 <h2>Input File Syntax</h2> | 272 <h2>Input File Syntax</h2> |
| 267 | 273 |
| 268 <p>The main purpose of the grammar specification file for Lemon is | 274 <p>The main purpose of the grammar specification file for Lemon is |
| 269 to define the grammar for the parser. But the input file also | 275 to define the grammar for the parser. But the input file also |
| 270 specifies additional information Lemon requires to do its job. | 276 specifies additional information Lemon requires to do its job. |
| 271 Most of the work in using Lemon is in writing an appropriate | 277 Most of the work in using Lemon is in writing an appropriate |
| 272 grammar file.</p> | 278 grammar file.</p> |
| 273 | 279 |
| 274 <p>The grammar file for lemon is, for the most part, free format. | 280 <p>The grammar file for lemon is, for the most part, free format. |
| 275 It does not have sections or divisions like yacc or bison. Any | 281 It does not have sections or divisions like yacc or bison. Any |
| 276 declaration can occur at any point in the file. | 282 declaration can occur at any point in the file. |
| 277 Lemon ignores whitespace (except where it is needed to separate | 283 Lemon ignores whitespace (except where it is needed to separate |
| 278 tokens) and it honors the same commenting conventions as C and C++.</p> | 284 tokens) and it honors the same commenting conventions as C and C++.</p> |
| 279 | 285 |
| 280 <h3>Terminals and Nonterminals</h3> | 286 <h3>Terminals and Nonterminals</h3> |
| 281 | 287 |
| 282 <p>A terminal symbol (token) is any string of alphanumeric | 288 <p>A terminal symbol (token) is any string of alphanumeric |
| 283 and underscore characters | 289 and/or underscore characters |
| 284 that begins with an upper case letter. | 290 that begins with an upper case letter. |
| 285 A terminal can contain lowercase letters after the first character, | 291 A terminal can contain lowercase letters after the first character, |
| 286 but the usual convention is to make terminals all upper case. | 292 but the usual convention is to make terminals all upper case. |
| 287 A nonterminal, on the other hand, is any string of alphanumeric | 293 A nonterminal, on the other hand, is any string of alphanumeric |
| 288 and underscore characters than begins with a lower case letter. | 294 and underscore characters than begins with a lower case letter. |
| 289 Again, the usual convention is to make nonterminals use all lower | 295 Again, the usual convention is to make nonterminals use all lower |
| 290 case letters.</p> | 296 case letters.</p> |
| 291 | 297 |
| 292 <p>In Lemon, terminal and nonterminal symbols do not need to | 298 <p>In Lemon, terminal and nonterminal symbols do not need to |
| 293 be declared or identified in a separate section of the grammar file. | 299 be declared or identified in a separate section of the grammar file. |
| 294 Lemon is able to generate a list of all terminals and nonterminals | 300 Lemon is able to generate a list of all terminals and nonterminals |
| 295 by examining the grammar rules, and it can always distinguish a | 301 by examining the grammar rules, and it can always distinguish a |
| 296 terminal from a nonterminal by checking the case of the first | 302 terminal from a nonterminal by checking the case of the first |
| 297 character of the name.</p> | 303 character of the name.</p> |
| 298 | 304 |
| 299 <p>Yacc and bison allow terminal symbols to have either alphanumeric | 305 <p>Yacc and bison allow terminal symbols to have either alphanumeric |
| 300 names or to be individual characters included in single quotes, like | 306 names or to be individual characters included in single quotes, like |
| 301 this: ')' or '$'. Lemon does not allow this alternative form for | 307 this: ')' or '$'. Lemon does not allow this alternative form for |
| 302 terminal symbols. With Lemon, all symbols, terminals and nonterminals, | 308 terminal symbols. With Lemon, all symbols, terminals and nonterminals, |
| 303 must have alphanumeric names.</p> | 309 must have alphanumeric names.</p> |
| 304 | 310 |
| 305 <h3>Grammar Rules</h3> | 311 <h3>Grammar Rules</h3> |
| 306 | 312 |
| 307 <p>The main component of a Lemon grammar file is a sequence of grammar | 313 <p>The main component of a Lemon grammar file is a sequence of grammar |
| 308 rules. | 314 rules. |
| 309 Each grammar rule consists of a nonterminal symbol followed by | 315 Each grammar rule consists of a nonterminal symbol followed by |
| 310 the special symbol ``::='' and then a list of terminals and/or nonterminals. | 316 the special symbol "::=" and then a list of terminals and/or nonterminals. |
| 311 The rule is terminated by a period. | 317 The rule is terminated by a period. |
| 312 The list of terminals and nonterminals on the right-hand side of the | 318 The list of terminals and nonterminals on the right-hand side of the |
| 313 rule can be empty. | 319 rule can be empty. |
| 314 Rules can occur in any order, except that the left-hand side of the | 320 Rules can occur in any order, except that the left-hand side of the |
| 315 first rule is assumed to be the start symbol for the grammar (unless | 321 first rule is assumed to be the start symbol for the grammar (unless |
| 316 specified otherwise using the <tt>%start</tt> directive described below.) | 322 specified otherwise using the <tt>%start</tt> directive described below.) |
| 317 A typical sequence of grammar rules might look something like this: | 323 A typical sequence of grammar rules might look something like this: |
| 318 <pre> | 324 <pre> |
| 319 expr ::= expr PLUS expr. | 325 expr ::= expr PLUS expr. |
| 320 expr ::= expr TIMES expr. | 326 expr ::= expr TIMES expr. |
| 321 expr ::= LPAREN expr RPAREN. | 327 expr ::= LPAREN expr RPAREN. |
| 322 expr ::= VALUE. | 328 expr ::= VALUE. |
| 323 </pre> | 329 </pre> |
| 324 </p> | 330 </p> |
| 325 | 331 |
| 326 <p>There is one non-terminal in this example, ``expr'', and five | 332 <p>There is one non-terminal in this example, "expr", and five |
| 327 terminal symbols or tokens: ``PLUS'', ``TIMES'', ``LPAREN'', | 333 terminal symbols or tokens: "PLUS", "TIMES", "LPAREN", |
| 328 ``RPAREN'' and ``VALUE''.</p> | 334 "RPAREN" and "VALUE".</p> |
| 329 | 335 |
| 330 <p>Like yacc and bison, Lemon allows the grammar to specify a block | 336 <p>Like yacc and bison, Lemon allows the grammar to specify a block |
| 331 of C code that will be executed whenever a grammar rule is reduced | 337 of C code that will be executed whenever a grammar rule is reduced |
| 332 by the parser. | 338 by the parser. |
| 333 In Lemon, this action is specified by putting the C code (contained | 339 In Lemon, this action is specified by putting the C code (contained |
| 334 within curly braces <tt>{...}</tt>) immediately after the | 340 within curly braces <tt>{...}</tt>) immediately after the |
| 335 period that closes the rule. | 341 period that closes the rule. |
| 336 For example: | 342 For example: |
| 337 <pre> | 343 <pre> |
| 338 expr ::= expr PLUS expr. { printf("Doing an addition...\n"); } | 344 expr ::= expr PLUS expr. { printf("Doing an addition...\n"); } |
| 339 </pre> | 345 </pre> |
| 340 </p> | 346 </p> |
| 341 | 347 |
| 342 <p>In order to be useful, grammar actions must normally be linked to | 348 <p>In order to be useful, grammar actions must normally be linked to |
| 343 their associated grammar rules. | 349 their associated grammar rules. |
| 344 In yacc and bison, this is accomplished by embedding a ``$$'' in the | 350 In yacc and bison, this is accomplished by embedding a "$$" in the |
| 345 action to stand for the value of the left-hand side of the rule and | 351 action to stand for the value of the left-hand side of the rule and |
| 346 symbols ``$1'', ``$2'', and so forth to stand for the value of | 352 symbols "$1", "$2", and so forth to stand for the value of |
| 347 the terminal or nonterminal at position 1, 2 and so forth on the | 353 the terminal or nonterminal at position 1, 2 and so forth on the |
| 348 right-hand side of the rule. | 354 right-hand side of the rule. |
| 349 This idea is very powerful, but it is also very error-prone. The | 355 This idea is very powerful, but it is also very error-prone. The |
| 350 single most common source of errors in a yacc or bison grammar is | 356 single most common source of errors in a yacc or bison grammar is |
| 351 to miscount the number of symbols on the right-hand side of a grammar | 357 to miscount the number of symbols on the right-hand side of a grammar |
| 352 rule and say ``$7'' when you really mean ``$8''.</p> | 358 rule and say "$7" when you really mean "$8".</p> |
| 353 | 359 |
| 354 <p>Lemon avoids the need to count grammar symbols by assigning symbolic | 360 <p>Lemon avoids the need to count grammar symbols by assigning symbolic |
| 355 names to each symbol in a grammar rule and then using those symbolic | 361 names to each symbol in a grammar rule and then using those symbolic |
| 356 names in the action. | 362 names in the action. |
| 357 In yacc or bison, one would write this: | 363 In yacc or bison, one would write this: |
| 358 <pre> | 364 <pre> |
| 359 expr -> expr PLUS expr { $$ = $1 + $3; }; | 365 expr -> expr PLUS expr { $$ = $1 + $3; }; |
| 360 </pre> | 366 </pre> |
| 361 But in Lemon, the same rule becomes the following: | 367 But in Lemon, the same rule becomes the following: |
| 362 <pre> | 368 <pre> |
| 363 expr(A) ::= expr(B) PLUS expr(C). { A = B+C; } | 369 expr(A) ::= expr(B) PLUS expr(C). { A = B+C; } |
| 364 </pre> | 370 </pre> |
| 365 In the Lemon rule, any symbol in parentheses after a grammar rule | 371 In the Lemon rule, any symbol in parentheses after a grammar rule |
| 366 symbol becomes a place holder for that symbol in the grammar rule. | 372 symbol becomes a place holder for that symbol in the grammar rule. |
| 367 This place holder can then be used in the associated C action to | 373 This place holder can then be used in the associated C action to |
| 368 stand for the value of that symbol.<p> | 374 stand for the value of that symbol.<p> |
| 369 | 375 |
| 370 <p>The Lemon notation for linking a grammar rule with its reduce | 376 <p>The Lemon notation for linking a grammar rule with its reduce |
| 371 action is superior to yacc/bison on several counts. | 377 action is superior to yacc/bison on several counts. |
| 372 First, as mentioned above, the Lemon method avoids the need to | 378 First, as mentioned above, the Lemon method avoids the need to |
| 373 count grammar symbols. | 379 count grammar symbols. |
| 374 Secondly, if a terminal or nonterminal in a Lemon grammar rule | 380 Secondly, if a terminal or nonterminal in a Lemon grammar rule |
| 375 includes a linking symbol in parentheses but that linking symbol | 381 includes a linking symbol in parentheses but that linking symbol |
| 376 is not actually used in the reduce action, then an error message | 382 is not actually used in the reduce action, then an error message |
| 377 is generated. | 383 is generated. |
| 378 For example, the rule | 384 For example, the rule |
| 379 <pre> | 385 <pre> |
| 380 expr(A) ::= expr(B) PLUS expr(C). { A = B; } | 386 expr(A) ::= expr(B) PLUS expr(C). { A = B; } |
| 381 </pre> | 387 </pre> |
| 382 will generate an error because the linking symbol ``C'' is used | 388 will generate an error because the linking symbol "C" is used |
| 383 in the grammar rule but not in the reduce action.</p> | 389 in the grammar rule but not in the reduce action.</p> |
| 384 | 390 |
| 385 <p>The Lemon notation for linking grammar rules to reduce actions | 391 <p>The Lemon notation for linking grammar rules to reduce actions |
| 386 also facilitates the use of destructors for reclaiming memory | 392 also facilitates the use of destructors for reclaiming memory |
| 387 allocated by the values of terminals and nonterminals on the | 393 allocated by the values of terminals and nonterminals on the |
| 388 right-hand side of a rule.</p> | 394 right-hand side of a rule.</p> |
| 389 | 395 |
| 396 <a name='precrules'></a> |
| 390 <h3>Precedence Rules</h3> | 397 <h3>Precedence Rules</h3> |
| 391 | 398 |
| 392 <p>Lemon resolves parsing ambiguities in exactly the same way as | 399 <p>Lemon resolves parsing ambiguities in exactly the same way as |
| 393 yacc and bison. A shift-reduce conflict is resolved in favor | 400 yacc and bison. A shift-reduce conflict is resolved in favor |
| 394 of the shift, and a reduce-reduce conflict is resolved by reducing | 401 of the shift, and a reduce-reduce conflict is resolved by reducing |
| 395 whichever rule comes first in the grammar file.</p> | 402 whichever rule comes first in the grammar file.</p> |
| 396 | 403 |
| 397 <p>Just like in | 404 <p>Just like in |
| 398 yacc and bison, Lemon allows a measure of control | 405 yacc and bison, Lemon allows a measure of control |
| 399 over the resolution of paring conflicts using precedence rules. | 406 over the resolution of paring conflicts using precedence rules. |
| 400 A precedence value can be assigned to any terminal symbol | 407 A precedence value can be assigned to any terminal symbol |
| 401 using the %left, %right or %nonassoc directives. Terminal symbols | 408 using the |
| 409 <a href='#pleft'>%left</a>, |
| 410 <a href='#pright'>%right</a> or |
| 411 <a href='#pnonassoc'>%nonassoc</a> directives. Terminal symbols |
| 402 mentioned in earlier directives have a lower precedence that | 412 mentioned in earlier directives have a lower precedence that |
| 403 terminal symbols mentioned in later directives. For example:</p> | 413 terminal symbols mentioned in later directives. For example:</p> |
| 404 | 414 |
| 405 <p><pre> | 415 <p><pre> |
| 406 %left AND. | 416 %left AND. |
| 407 %left OR. | 417 %left OR. |
| 408 %nonassoc EQ NE GT GE LT LE. | 418 %nonassoc EQ NE GT GE LT LE. |
| 409 %left PLUS MINUS. | 419 %left PLUS MINUS. |
| 410 %left TIMES DIVIDE MOD. | 420 %left TIMES DIVIDE MOD. |
| 411 %right EXP NOT. | 421 %right EXP NOT. |
| (...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 511 grammar rules. It doesn't matter. The relative order of | 521 grammar rules. It doesn't matter. The relative order of |
| 512 directives used to assign precedence to terminals is important, but | 522 directives used to assign precedence to terminals is important, but |
| 513 other than that, the order of directives in Lemon is arbitrary.</p> | 523 other than that, the order of directives in Lemon is arbitrary.</p> |
| 514 | 524 |
| 515 <p>Lemon supports the following special directives: | 525 <p>Lemon supports the following special directives: |
| 516 <ul> | 526 <ul> |
| 517 <li><tt>%code</tt> | 527 <li><tt>%code</tt> |
| 518 <li><tt>%default_destructor</tt> | 528 <li><tt>%default_destructor</tt> |
| 519 <li><tt>%default_type</tt> | 529 <li><tt>%default_type</tt> |
| 520 <li><tt>%destructor</tt> | 530 <li><tt>%destructor</tt> |
| 531 <li><tt>%endif</tt> |
| 521 <li><tt>%extra_argument</tt> | 532 <li><tt>%extra_argument</tt> |
| 533 <li><tt>%fallback</tt> |
| 534 <li><tt>%ifdef</tt> |
| 535 <li><tt>%ifndef</tt> |
| 522 <li><tt>%include</tt> | 536 <li><tt>%include</tt> |
| 523 <li><tt>%left</tt> | 537 <li><tt>%left</tt> |
| 524 <li><tt>%name</tt> | 538 <li><tt>%name</tt> |
| 525 <li><tt>%nonassoc</tt> | 539 <li><tt>%nonassoc</tt> |
| 526 <li><tt>%parse_accept</tt> | 540 <li><tt>%parse_accept</tt> |
| 527 <li><tt>%parse_failure </tt> | 541 <li><tt>%parse_failure </tt> |
| 528 <li><tt>%right</tt> | 542 <li><tt>%right</tt> |
| 529 <li><tt>%stack_overflow</tt> | 543 <li><tt>%stack_overflow</tt> |
| 530 <li><tt>%stack_size</tt> | 544 <li><tt>%stack_size</tt> |
| 531 <li><tt>%start_symbol</tt> | 545 <li><tt>%start_symbol</tt> |
| 532 <li><tt>%syntax_error</tt> | 546 <li><tt>%syntax_error</tt> |
| 547 <li><tt>%token_class</tt> |
| 533 <li><tt>%token_destructor</tt> | 548 <li><tt>%token_destructor</tt> |
| 534 <li><tt>%token_prefix</tt> | 549 <li><tt>%token_prefix</tt> |
| 535 <li><tt>%token_type</tt> | 550 <li><tt>%token_type</tt> |
| 536 <li><tt>%type</tt> | 551 <li><tt>%type</tt> |
| 552 <li><tt>%wildcard</tt> |
| 537 </ul> | 553 </ul> |
| 538 Each of these directives will be described separately in the | 554 Each of these directives will be described separately in the |
| 539 following sections:</p> | 555 following sections:</p> |
| 540 | 556 |
| 557 <a name='pcode'></a> |
| 541 <h4>The <tt>%code</tt> directive</h4> | 558 <h4>The <tt>%code</tt> directive</h4> |
| 542 | 559 |
| 543 <p>The %code directive is used to specify addition C/C++ code that | 560 <p>The %code directive is used to specify addition C code that |
| 544 is added to the end of the main output file. This is similar to | 561 is added to the end of the main output file. This is similar to |
| 545 the %include directive except that %include is inserted at the | 562 the <a href='#pinclude'>%include</a> directive except that %include |
| 546 beginning of the main output file.</p> | 563 is inserted at the beginning of the main output file.</p> |
| 547 | 564 |
| 548 <p>%code is typically used to include some action routines or perhaps | 565 <p>%code is typically used to include some action routines or perhaps |
| 549 a tokenizer as part of the output file.</p> | 566 a tokenizer or even the "main()" function |
| 567 as part of the output file.</p> |
| 550 | 568 |
| 569 <a name='default_destructor'></a> |
| 551 <h4>The <tt>%default_destructor</tt> directive</h4> | 570 <h4>The <tt>%default_destructor</tt> directive</h4> |
| 552 | 571 |
| 553 <p>The %default_destructor directive specifies a destructor to | 572 <p>The %default_destructor directive specifies a destructor to |
| 554 use for non-terminals that do not have their own destructor | 573 use for non-terminals that do not have their own destructor |
| 555 specified by a separate %destructor directive. See the documentation | 574 specified by a separate %destructor directive. See the documentation |
| 556 on the %destructor directive below for additional information.</p> | 575 on the <a name='#destructor'>%destructor</a> directive below for |
| 576 additional information.</p> |
| 557 | 577 |
| 558 <p>In some grammers, many different non-terminal symbols have the | 578 <p>In some grammers, many different non-terminal symbols have the |
| 559 same datatype and hence the same destructor. This directive is | 579 same datatype and hence the same destructor. This directive is |
| 560 a convenience way to specify the same destructor for all those | 580 a convenience way to specify the same destructor for all those |
| 561 non-terminals using a single statement.</p> | 581 non-terminals using a single statement.</p> |
| 562 | 582 |
| 583 <a name='default_type'></a> |
| 563 <h4>The <tt>%default_type</tt> directive</h4> | 584 <h4>The <tt>%default_type</tt> directive</h4> |
| 564 | 585 |
| 565 <p>The %default_type directive specifies the datatype of non-terminal | 586 <p>The %default_type directive specifies the datatype of non-terminal |
| 566 symbols that do no have their own datatype defined using a separate | 587 symbols that do no have their own datatype defined using a separate |
| 567 %type directive. See the documentation on %type below for addition | 588 <a href='#ptype'>%type</a> directive. |
| 568 information.</p> | 589 </p> |
| 569 | 590 |
| 591 <a name='destructor'></a> |
| 570 <h4>The <tt>%destructor</tt> directive</h4> | 592 <h4>The <tt>%destructor</tt> directive</h4> |
| 571 | 593 |
| 572 <p>The %destructor directive is used to specify a destructor for | 594 <p>The %destructor directive is used to specify a destructor for |
| 573 a non-terminal symbol. | 595 a non-terminal symbol. |
| 574 (See also the %token_destructor directive which is used to | 596 (See also the <a href='#token_destructor'>%token_destructor</a> |
| 575 specify a destructor for terminal symbols.)</p> | 597 directive which is used to specify a destructor for terminal symbols.)</p> |
| 576 | 598 |
| 577 <p>A non-terminal's destructor is called to dispose of the | 599 <p>A non-terminal's destructor is called to dispose of the |
| 578 non-terminal's value whenever the non-terminal is popped from | 600 non-terminal's value whenever the non-terminal is popped from |
| 579 the stack. This includes all of the following circumstances: | 601 the stack. This includes all of the following circumstances: |
| 580 <ul> | 602 <ul> |
| 581 <li> When a rule reduces and the value of a non-terminal on | 603 <li> When a rule reduces and the value of a non-terminal on |
| 582 the right-hand side is not linked to C code. | 604 the right-hand side is not linked to C code. |
| 583 <li> When the stack is popped during error processing. | 605 <li> When the stack is popped during error processing. |
| 584 <li> When the ParseFree() function runs. | 606 <li> When the ParseFree() function runs. |
| 585 </ul> | 607 </ul> |
| 586 The destructor can do whatever it wants with the value of | 608 The destructor can do whatever it wants with the value of |
| 587 the non-terminal, but its design is to deallocate memory | 609 the non-terminal, but its design is to deallocate memory |
| 588 or other resources held by that non-terminal.</p> | 610 or other resources held by that non-terminal.</p> |
| 589 | 611 |
| 590 <p>Consider an example: | 612 <p>Consider an example: |
| 591 <pre> | 613 <pre> |
| 592 %type nt {void*} | 614 %type nt {void*} |
| 593 %destructor nt { free($$); } | 615 %destructor nt { free($$); } |
| 594 nt(A) ::= ID NUM. { A = malloc( 100 ); } | 616 nt(A) ::= ID NUM. { A = malloc( 100 ); } |
| 595 </pre> | 617 </pre> |
| 596 This example is a bit contrived but it serves to illustrate how | 618 This example is a bit contrived but it serves to illustrate how |
| 597 destructors work. The example shows a non-terminal named | 619 destructors work. The example shows a non-terminal named |
| 598 ``nt'' that holds values of type ``void*''. When the rule for | 620 "nt" that holds values of type "void*". When the rule for |
| 599 an ``nt'' reduces, it sets the value of the non-terminal to | 621 an "nt" reduces, it sets the value of the non-terminal to |
| 600 space obtained from malloc(). Later, when the nt non-terminal | 622 space obtained from malloc(). Later, when the nt non-terminal |
| 601 is popped from the stack, the destructor will fire and call | 623 is popped from the stack, the destructor will fire and call |
| 602 free() on this malloced space, thus avoiding a memory leak. | 624 free() on this malloced space, thus avoiding a memory leak. |
| 603 (Note that the symbol ``$$'' in the destructor code is replaced | 625 (Note that the symbol "$$" in the destructor code is replaced |
| 604 by the value of the non-terminal.)</p> | 626 by the value of the non-terminal.)</p> |
| 605 | 627 |
| 606 <p>It is important to note that the value of a non-terminal is passed | 628 <p>It is important to note that the value of a non-terminal is passed |
| 607 to the destructor whenever the non-terminal is removed from the | 629 to the destructor whenever the non-terminal is removed from the |
| 608 stack, unless the non-terminal is used in a C-code action. If | 630 stack, unless the non-terminal is used in a C-code action. If |
| 609 the non-terminal is used by C-code, then it is assumed that the | 631 the non-terminal is used by C-code, then it is assumed that the |
| 610 C-code will take care of destroying it if it should really | 632 C-code will take care of destroying it. |
| 611 be destroyed. More commonly, the value is used to build some | 633 More commonly, the value is used to build some |
| 612 larger structure and we don't want to destroy it, which is why | 634 larger structure and we don't want to destroy it, which is why |
| 613 the destructor is not called in this circumstance.</p> | 635 the destructor is not called in this circumstance.</p> |
| 614 | 636 |
| 615 <p>By appropriate use of destructors, it is possible to | 637 <p>Destructors help avoid memory leaks by automatically freeing |
| 616 build a parser using Lemon that can be used within a long-running | 638 allocated objects when they go out of scope. |
| 617 program, such as a GUI, that will not leak memory or other resources. | |
| 618 To do the same using yacc or bison is much more difficult.</p> | 639 To do the same using yacc or bison is much more difficult.</p> |
| 619 | 640 |
| 641 <a name="extraarg"></a> |
| 620 <h4>The <tt>%extra_argument</tt> directive</h4> | 642 <h4>The <tt>%extra_argument</tt> directive</h4> |
| 621 | 643 |
| 622 The %extra_argument directive instructs Lemon to add a 4th parameter | 644 The %extra_argument directive instructs Lemon to add a 4th parameter |
| 623 to the parameter list of the Parse() function it generates. Lemon | 645 to the parameter list of the Parse() function it generates. Lemon |
| 624 doesn't do anything itself with this extra argument, but it does | 646 doesn't do anything itself with this extra argument, but it does |
| 625 make the argument available to C-code action routines, destructors, | 647 make the argument available to C-code action routines, destructors, |
| 626 and so forth. For example, if the grammar file contains:</p> | 648 and so forth. For example, if the grammar file contains:</p> |
| 627 | 649 |
| 628 <p><pre> | 650 <p><pre> |
| 629 %extra_argument { MyStruct *pAbc } | 651 %extra_argument { MyStruct *pAbc } |
| 630 </pre></p> | 652 </pre></p> |
| 631 | 653 |
| 632 <p>Then the Parse() function generated will have an 4th parameter | 654 <p>Then the Parse() function generated will have an 4th parameter |
| 633 of type ``MyStruct*'' and all action routines will have access to | 655 of type "MyStruct*" and all action routines will have access to |
| 634 a variable named ``pAbc'' that is the value of the 4th parameter | 656 a variable named "pAbc" that is the value of the 4th parameter |
| 635 in the most recent call to Parse().</p> | 657 in the most recent call to Parse().</p> |
| 636 | 658 |
| 659 <a name='pfallback'></a> |
| 660 <h4>The <tt>%fallback</tt> directive</h4> |
| 661 |
| 662 <p>The %fallback directive specifies an alternative meaning for one |
| 663 or more tokens. The alternative meaning is tried if the original token |
| 664 would have generated a syntax error. |
| 665 |
| 666 <p>The %fallback directive was added to support robust parsing of SQL |
| 667 syntax in <a href="https://www.sqlite.org/">SQLite</a>. |
| 668 The SQL language contains a large assortment of keywords, each of which |
| 669 appears as a different token to the language parser. SQL contains so |
| 670 many keywords, that it can be difficult for programmers to keep up with |
| 671 them all. Programmers will, therefore, sometimes mistakenly use an |
| 672 obscure language keyword for an identifier. The %fallback directive |
| 673 provides a mechanism to tell the parser: "If you are unable to parse |
| 674 this keyword, try treating it as an identifier instead." |
| 675 |
| 676 <p>The syntax of %fallback is as follows: |
| 677 |
| 678 <blockquote> |
| 679 <tt>%fallback</tt> <i>ID</i> <i>TOKEN...</i> <b>.</b> |
| 680 </blockquote> |
| 681 |
| 682 <p>In words, the %fallback directive is followed by a list of token names |
| 683 terminated by a period. The first token name is the fallback token - the |
| 684 token to which all the other tokens fall back to. The second and subsequent |
| 685 arguments are tokens which fall back to the token identified by the first |
| 686 argument. |
| 687 |
| 688 <a name='pifdef'></a> |
| 689 <h4>The <tt>%ifdef</tt>, <tt>%ifndef</tt>, and <tt>%endif</tt> directives.</h4> |
| 690 |
| 691 <p>The %ifdef, %ifndef, and %endif directives are similar to |
| 692 #ifdef, #ifndef, and #endif in the C-preprocessor, just not as general. |
| 693 Each of these directives must begin at the left margin. No whitespace |
| 694 is allowed between the "%" and the directive name. |
| 695 |
| 696 <p>Grammar text in between "%ifdef MACRO" and the next nested "%endif" is |
| 697 ignored unless the "-DMACRO" command-line option is used. Grammar text |
| 698 betwen "%ifndef MACRO" and the next nested "%endif" is included except when |
| 699 the "-DMACRO" command-line option is used. |
| 700 |
| 701 <p>Note that the argument to %ifdef and %ifndef must be a single |
| 702 preprocessor symbol name, not a general expression. There is no "%else" |
| 703 directive. |
| 704 |
| 705 |
| 706 <a name='pinclude'></a> |
| 637 <h4>The <tt>%include</tt> directive</h4> | 707 <h4>The <tt>%include</tt> directive</h4> |
| 638 | 708 |
| 639 <p>The %include directive specifies C code that is included at the | 709 <p>The %include directive specifies C code that is included at the |
| 640 top of the generated parser. You can include any text you want -- | 710 top of the generated parser. You can include any text you want -- |
| 641 the Lemon parser generator copies it blindly. If you have multiple | 711 the Lemon parser generator copies it blindly. If you have multiple |
| 642 %include directives in your grammar file the value of the last | 712 %include directives in your grammar file, their values are concatenated |
| 643 %include directive overwrites all the others.</p. | 713 so that all %include code ultimately appears near the top of the |
| 714 generated parser, in the same order as it appeared in the grammer.</p> |
| 644 | 715 |
| 645 <p>The %include directive is very handy for getting some extra #include | 716 <p>The %include directive is very handy for getting some extra #include |
| 646 preprocessor statements at the beginning of the generated parser. | 717 preprocessor statements at the beginning of the generated parser. |
| 647 For example:</p> | 718 For example:</p> |
| 648 | 719 |
| 649 <p><pre> | 720 <p><pre> |
| 650 %include {#include <unistd.h>} | 721 %include {#include <unistd.h>} |
| 651 </pre></p> | 722 </pre></p> |
| 652 | 723 |
| 653 <p>This might be needed, for example, if some of the C actions in the | 724 <p>This might be needed, for example, if some of the C actions in the |
| 654 grammar call functions that are prototyed in unistd.h.</p> | 725 grammar call functions that are prototyed in unistd.h.</p> |
| 655 | 726 |
| 727 <a name='pleft'></a> |
| 656 <h4>The <tt>%left</tt> directive</h4> | 728 <h4>The <tt>%left</tt> directive</h4> |
| 657 | 729 |
| 658 The %left directive is used (along with the %right and | 730 The %left directive is used (along with the <a href='#pright'>%right</a> and |
| 659 %nonassoc directives) to declare precedences of terminal | 731 <a href='#pnonassoc'>%nonassoc</a> directives) to declare precedences of |
| 660 symbols. Every terminal symbol whose name appears after | 732 terminal symbols. Every terminal symbol whose name appears after |
| 661 a %left directive but before the next period (``.'') is | 733 a %left directive but before the next period (".") is |
| 662 given the same left-associative precedence value. Subsequent | 734 given the same left-associative precedence value. Subsequent |
| 663 %left directives have higher precedence. For example:</p> | 735 %left directives have higher precedence. For example:</p> |
| 664 | 736 |
| 665 <p><pre> | 737 <p><pre> |
| 666 %left AND. | 738 %left AND. |
| 667 %left OR. | 739 %left OR. |
| 668 %nonassoc EQ NE GT GE LT LE. | 740 %nonassoc EQ NE GT GE LT LE. |
| 669 %left PLUS MINUS. | 741 %left PLUS MINUS. |
| 670 %left TIMES DIVIDE MOD. | 742 %left TIMES DIVIDE MOD. |
| 671 %right EXP NOT. | 743 %right EXP NOT. |
| 672 </pre></p> | 744 </pre></p> |
| 673 | 745 |
| 674 <p>Note the period that terminates each %left, %right or %nonassoc | 746 <p>Note the period that terminates each %left, %right or %nonassoc |
| 675 directive.</p> | 747 directive.</p> |
| 676 | 748 |
| 677 <p>LALR(1) grammars can get into a situation where they require | 749 <p>LALR(1) grammars can get into a situation where they require |
| 678 a large amount of stack space if you make heavy use or right-associative | 750 a large amount of stack space if you make heavy use or right-associative |
| 679 operators. For this reason, it is recommended that you use %left | 751 operators. For this reason, it is recommended that you use %left |
| 680 rather than %right whenever possible.</p> | 752 rather than %right whenever possible.</p> |
| 681 | 753 |
| 754 <a name='pname'></a> |
| 682 <h4>The <tt>%name</tt> directive</h4> | 755 <h4>The <tt>%name</tt> directive</h4> |
| 683 | 756 |
| 684 <p>By default, the functions generated by Lemon all begin with the | 757 <p>By default, the functions generated by Lemon all begin with the |
| 685 five-character string ``Parse''. You can change this string to something | 758 five-character string "Parse". You can change this string to something |
| 686 different using the %name directive. For instance:</p> | 759 different using the %name directive. For instance:</p> |
| 687 | 760 |
| 688 <p><pre> | 761 <p><pre> |
| 689 %name Abcde | 762 %name Abcde |
| 690 </pre></p> | 763 </pre></p> |
| 691 | 764 |
| 692 <p>Putting this directive in the grammar file will cause Lemon to generate | 765 <p>Putting this directive in the grammar file will cause Lemon to generate |
| 693 functions named | 766 functions named |
| 694 <ul> | 767 <ul> |
| 695 <li> AbcdeAlloc(), | 768 <li> AbcdeAlloc(), |
| 696 <li> AbcdeFree(), | 769 <li> AbcdeFree(), |
| 697 <li> AbcdeTrace(), and | 770 <li> AbcdeTrace(), and |
| 698 <li> Abcde(). | 771 <li> Abcde(). |
| 699 </ul> | 772 </ul> |
| 700 The %name directive allows you to generator two or more different | 773 The %name directive allows you to generator two or more different |
| 701 parsers and link them all into the same executable. | 774 parsers and link them all into the same executable. |
| 702 </p> | 775 </p> |
| 703 | 776 |
| 777 <a name='pnonassoc'></a> |
| 704 <h4>The <tt>%nonassoc</tt> directive</h4> | 778 <h4>The <tt>%nonassoc</tt> directive</h4> |
| 705 | 779 |
| 706 <p>This directive is used to assign non-associative precedence to | 780 <p>This directive is used to assign non-associative precedence to |
| 707 one or more terminal symbols. See the section on precedence rules | 781 one or more terminal symbols. See the section on |
| 708 or on the %left directive for additional information.</p> | 782 <a href='#precrules'>precedence rules</a> |
| 783 or on the <a href='#pleft'>%left</a> directive for additional information.</p> |
| 709 | 784 |
| 785 <a name='parse_accept'></a> |
| 710 <h4>The <tt>%parse_accept</tt> directive</h4> | 786 <h4>The <tt>%parse_accept</tt> directive</h4> |
| 711 | 787 |
| 712 <p>The %parse_accept directive specifies a block of C code that is | 788 <p>The %parse_accept directive specifies a block of C code that is |
| 713 executed whenever the parser accepts its input string. To ``accept'' | 789 executed whenever the parser accepts its input string. To "accept" |
| 714 an input string means that the parser was able to process all tokens | 790 an input string means that the parser was able to process all tokens |
| 715 without error.</p> | 791 without error.</p> |
| 716 | 792 |
| 717 <p>For example:</p> | 793 <p>For example:</p> |
| 718 | 794 |
| 719 <p><pre> | 795 <p><pre> |
| 720 %parse_accept { | 796 %parse_accept { |
| 721 printf("parsing complete!\n"); | 797 printf("parsing complete!\n"); |
| 722 } | 798 } |
| 723 </pre></p> | 799 </pre></p> |
| 724 | 800 |
| 725 | 801 <a name='parse_failure'></a> |
| 726 <h4>The <tt>%parse_failure</tt> directive</h4> | 802 <h4>The <tt>%parse_failure</tt> directive</h4> |
| 727 | 803 |
| 728 <p>The %parse_failure directive specifies a block of C code that | 804 <p>The %parse_failure directive specifies a block of C code that |
| 729 is executed whenever the parser fails complete. This code is not | 805 is executed whenever the parser fails complete. This code is not |
| 730 executed until the parser has tried and failed to resolve an input | 806 executed until the parser has tried and failed to resolve an input |
| 731 error using is usual error recovery strategy. The routine is | 807 error using is usual error recovery strategy. The routine is |
| 732 only invoked when parsing is unable to continue.</p> | 808 only invoked when parsing is unable to continue.</p> |
| 733 | 809 |
| 734 <p><pre> | 810 <p><pre> |
| 735 %parse_failure { | 811 %parse_failure { |
| 736 fprintf(stderr,"Giving up. Parser is hopelessly lost...\n"); | 812 fprintf(stderr,"Giving up. Parser is hopelessly lost...\n"); |
| 737 } | 813 } |
| 738 </pre></p> | 814 </pre></p> |
| 739 | 815 |
| 816 <a name='pright'></a> |
| 740 <h4>The <tt>%right</tt> directive</h4> | 817 <h4>The <tt>%right</tt> directive</h4> |
| 741 | 818 |
| 742 <p>This directive is used to assign right-associative precedence to | 819 <p>This directive is used to assign right-associative precedence to |
| 743 one or more terminal symbols. See the section on precedence rules | 820 one or more terminal symbols. See the section on |
| 744 or on the %left directive for additional information.</p> | 821 <a href='#precrules'>precedence rules</a> |
| 822 or on the <a href='#pleft'>%left</a> directive for additional information.</p> |
| 745 | 823 |
| 824 <a name='stack_overflow'></a> |
| 746 <h4>The <tt>%stack_overflow</tt> directive</h4> | 825 <h4>The <tt>%stack_overflow</tt> directive</h4> |
| 747 | 826 |
| 748 <p>The %stack_overflow directive specifies a block of C code that | 827 <p>The %stack_overflow directive specifies a block of C code that |
| 749 is executed if the parser's internal stack ever overflows. Typically | 828 is executed if the parser's internal stack ever overflows. Typically |
| 750 this just prints an error message. After a stack overflow, the parser | 829 this just prints an error message. After a stack overflow, the parser |
| 751 will be unable to continue and must be reset.</p> | 830 will be unable to continue and must be reset.</p> |
| 752 | 831 |
| 753 <p><pre> | 832 <p><pre> |
| 754 %stack_overflow { | 833 %stack_overflow { |
| 755 fprintf(stderr,"Giving up. Parser stack overflow\n"); | 834 fprintf(stderr,"Giving up. Parser stack overflow\n"); |
| 756 } | 835 } |
| 757 </pre></p> | 836 </pre></p> |
| 758 | 837 |
| 759 <p>You can help prevent parser stack overflows by avoiding the use | 838 <p>You can help prevent parser stack overflows by avoiding the use |
| 760 of right recursion and right-precedence operators in your grammar. | 839 of right recursion and right-precedence operators in your grammar. |
| 761 Use left recursion and and left-precedence operators instead, to | 840 Use left recursion and and left-precedence operators instead, to |
| 762 encourage rules to reduce sooner and keep the stack size down. | 841 encourage rules to reduce sooner and keep the stack size down. |
| 763 For example, do rules like this: | 842 For example, do rules like this: |
| 764 <pre> | 843 <pre> |
| 765 list ::= list element. // left-recursion. Good! | 844 list ::= list element. // left-recursion. Good! |
| 766 list ::= . | 845 list ::= . |
| 767 </pre> | 846 </pre> |
| 768 Not like this: | 847 Not like this: |
| 769 <pre> | 848 <pre> |
| 770 list ::= element list. // right-recursion. Bad! | 849 list ::= element list. // right-recursion. Bad! |
| 771 list ::= . | 850 list ::= . |
| 772 </pre> | 851 </pre> |
| 773 | 852 |
| 853 <a name='stack_size'></a> |
| 774 <h4>The <tt>%stack_size</tt> directive</h4> | 854 <h4>The <tt>%stack_size</tt> directive</h4> |
| 775 | 855 |
| 776 <p>If stack overflow is a problem and you can't resolve the trouble | 856 <p>If stack overflow is a problem and you can't resolve the trouble |
| 777 by using left-recursion, then you might want to increase the size | 857 by using left-recursion, then you might want to increase the size |
| 778 of the parser's stack using this directive. Put an positive integer | 858 of the parser's stack using this directive. Put an positive integer |
| 779 after the %stack_size directive and Lemon will generate a parse | 859 after the %stack_size directive and Lemon will generate a parse |
| 780 with a stack of the requested size. The default value is 100.</p> | 860 with a stack of the requested size. The default value is 100.</p> |
| 781 | 861 |
| 782 <p><pre> | 862 <p><pre> |
| 783 %stack_size 2000 | 863 %stack_size 2000 |
| 784 </pre></p> | 864 </pre></p> |
| 785 | 865 |
| 866 <a name='start_symbol'></a> |
| 786 <h4>The <tt>%start_symbol</tt> directive</h4> | 867 <h4>The <tt>%start_symbol</tt> directive</h4> |
| 787 | 868 |
| 788 <p>By default, the start-symbol for the grammar that Lemon generates | 869 <p>By default, the start-symbol for the grammar that Lemon generates |
| 789 is the first non-terminal that appears in the grammar file. But you | 870 is the first non-terminal that appears in the grammar file. But you |
| 790 can choose a different start-symbol using the %start_symbol directive.</p> | 871 can choose a different start-symbol using the %start_symbol directive.</p> |
| 791 | 872 |
| 792 <p><pre> | 873 <p><pre> |
| 793 %start_symbol prog | 874 %start_symbol prog |
| 794 </pre></p> | 875 </pre></p> |
| 795 | 876 |
| 877 <a name='token_destructor'></a> |
| 796 <h4>The <tt>%token_destructor</tt> directive</h4> | 878 <h4>The <tt>%token_destructor</tt> directive</h4> |
| 797 | 879 |
| 798 <p>The %destructor directive assigns a destructor to a non-terminal | 880 <p>The %destructor directive assigns a destructor to a non-terminal |
| 799 symbol. (See the description of the %destructor directive above.) | 881 symbol. (See the description of the %destructor directive above.) |
| 800 This directive does the same thing for all terminal symbols.</p> | 882 This directive does the same thing for all terminal symbols.</p> |
| 801 | 883 |
| 802 <p>Unlike non-terminal symbols which may each have a different data type | 884 <p>Unlike non-terminal symbols which may each have a different data type |
| 803 for their values, terminals all use the same data type (defined by | 885 for their values, terminals all use the same data type (defined by |
| 804 the %token_type directive) and so they use a common destructor. Other | 886 the %token_type directive) and so they use a common destructor. Other |
| 805 than that, the token destructor works just like the non-terminal | 887 than that, the token destructor works just like the non-terminal |
| 806 destructors.</p> | 888 destructors.</p> |
| 807 | 889 |
| 890 <a name='token_prefix'></a> |
| 808 <h4>The <tt>%token_prefix</tt> directive</h4> | 891 <h4>The <tt>%token_prefix</tt> directive</h4> |
| 809 | 892 |
| 810 <p>Lemon generates #defines that assign small integer constants | 893 <p>Lemon generates #defines that assign small integer constants |
| 811 to each terminal symbol in the grammar. If desired, Lemon will | 894 to each terminal symbol in the grammar. If desired, Lemon will |
| 812 add a prefix specified by this directive | 895 add a prefix specified by this directive |
| 813 to each of the #defines it generates. | 896 to each of the #defines it generates. |
| 814 So if the default output of Lemon looked like this: | 897 So if the default output of Lemon looked like this: |
| 815 <pre> | 898 <pre> |
| 816 #define AND 1 | 899 #define AND 1 |
| 817 #define MINUS 2 | 900 #define MINUS 2 |
| 818 #define OR 3 | 901 #define OR 3 |
| 819 #define PLUS 4 | 902 #define PLUS 4 |
| 820 </pre> | 903 </pre> |
| 821 You can insert a statement into the grammar like this: | 904 You can insert a statement into the grammar like this: |
| 822 <pre> | 905 <pre> |
| 823 %token_prefix TOKEN_ | 906 %token_prefix TOKEN_ |
| 824 </pre> | 907 </pre> |
| 825 to cause Lemon to produce these symbols instead: | 908 to cause Lemon to produce these symbols instead: |
| 826 <pre> | 909 <pre> |
| 827 #define TOKEN_AND 1 | 910 #define TOKEN_AND 1 |
| 828 #define TOKEN_MINUS 2 | 911 #define TOKEN_MINUS 2 |
| 829 #define TOKEN_OR 3 | 912 #define TOKEN_OR 3 |
| 830 #define TOKEN_PLUS 4 | 913 #define TOKEN_PLUS 4 |
| 831 </pre> | 914 </pre> |
| 832 | 915 |
| 916 <a name='token_type'></a><a name='ptype'></a> |
| 833 <h4>The <tt>%token_type</tt> and <tt>%type</tt> directives</h4> | 917 <h4>The <tt>%token_type</tt> and <tt>%type</tt> directives</h4> |
| 834 | 918 |
| 835 <p>These directives are used to specify the data types for values | 919 <p>These directives are used to specify the data types for values |
| 836 on the parser's stack associated with terminal and non-terminal | 920 on the parser's stack associated with terminal and non-terminal |
| 837 symbols. The values of all terminal symbols must be of the same | 921 symbols. The values of all terminal symbols must be of the same |
| 838 type. This turns out to be the same data type as the 3rd parameter | 922 type. This turns out to be the same data type as the 3rd parameter |
| 839 to the Parse() function generated by Lemon. Typically, you will | 923 to the Parse() function generated by Lemon. Typically, you will |
| 840 make the value of a terminal symbol by a pointer to some kind of | 924 make the value of a terminal symbol by a pointer to some kind of |
| 841 token structure. Like this:</p> | 925 token structure. Like this:</p> |
| 842 | 926 |
| 843 <p><pre> | 927 <p><pre> |
| 844 %token_type {Token*} | 928 %token_type {Token*} |
| 845 </pre></p> | 929 </pre></p> |
| 846 | 930 |
| 847 <p>If the data type of terminals is not specified, the default value | 931 <p>If the data type of terminals is not specified, the default value |
| 848 is ``int''.</p> | 932 is "void*".</p> |
| 849 | 933 |
| 850 <p>Non-terminal symbols can each have their own data types. Typically | 934 <p>Non-terminal symbols can each have their own data types. Typically |
| 851 the data type of a non-terminal is a pointer to the root of a parse-tree | 935 the data type of a non-terminal is a pointer to the root of a parse-tree |
| 852 structure that contains all information about that non-terminal. | 936 structure that contains all information about that non-terminal. |
| 853 For example:</p> | 937 For example:</p> |
| 854 | 938 |
| 855 <p><pre> | 939 <p><pre> |
| 856 %type expr {Expr*} | 940 %type expr {Expr*} |
| 857 </pre></p> | 941 </pre></p> |
| 858 | 942 |
| 859 <p>Each entry on the parser's stack is actually a union containing | 943 <p>Each entry on the parser's stack is actually a union containing |
| 860 instances of all data types for every non-terminal and terminal symbol. | 944 instances of all data types for every non-terminal and terminal symbol. |
| 861 Lemon will automatically use the correct element of this union depending | 945 Lemon will automatically use the correct element of this union depending |
| 862 on what the corresponding non-terminal or terminal symbol is. But | 946 on what the corresponding non-terminal or terminal symbol is. But |
| 863 the grammar designer should keep in mind that the size of the union | 947 the grammar designer should keep in mind that the size of the union |
| 864 will be the size of its largest element. So if you have a single | 948 will be the size of its largest element. So if you have a single |
| 865 non-terminal whose data type requires 1K of storage, then your 100 | 949 non-terminal whose data type requires 1K of storage, then your 100 |
| 866 entry parser stack will require 100K of heap space. If you are willing | 950 entry parser stack will require 100K of heap space. If you are willing |
| 867 and able to pay that price, fine. You just need to know.</p> | 951 and able to pay that price, fine. You just need to know.</p> |
| 868 | 952 |
| 953 <a name='pwildcard'></a> |
| 954 <h4>The <tt>%wildcard</tt> directive</h4> |
| 955 |
| 956 <p>The %wildcard directive is followed by a single token name and a |
| 957 period. This directive specifies that the identified token should |
| 958 match any input token. |
| 959 |
| 960 <p>When the generated parser has the choice of matching an input against |
| 961 the wildcard token and some other token, the other token is always used. |
| 962 The wildcard token is only matched if there are no other alternatives. |
| 963 |
| 869 <h3>Error Processing</h3> | 964 <h3>Error Processing</h3> |
| 870 | 965 |
| 871 <p>After extensive experimentation over several years, it has been | 966 <p>After extensive experimentation over several years, it has been |
| 872 discovered that the error recovery strategy used by yacc is about | 967 discovered that the error recovery strategy used by yacc is about |
| 873 as good as it gets. And so that is what Lemon uses.</p> | 968 as good as it gets. And so that is what Lemon uses.</p> |
| 874 | 969 |
| 875 <p>When a Lemon-generated parser encounters a syntax error, it | 970 <p>When a Lemon-generated parser encounters a syntax error, it |
| 876 first invokes the code specified by the %syntax_error directive, if | 971 first invokes the code specified by the %syntax_error directive, if |
| 877 any. It then enters its error recovery strategy. The error recovery | 972 any. It then enters its error recovery strategy. The error recovery |
| 878 strategy is to begin popping the parsers stack until it enters a | 973 strategy is to begin popping the parsers stack until it enters a |
| 879 state where it is permitted to shift a special non-terminal symbol | 974 state where it is permitted to shift a special non-terminal symbol |
| 880 named ``error''. It then shifts this non-terminal and continues | 975 named "error". It then shifts this non-terminal and continues |
| 881 parsing. But the %syntax_error routine will not be called again | 976 parsing. But the %syntax_error routine will not be called again |
| 882 until at least three new tokens have been successfully shifted.</p> | 977 until at least three new tokens have been successfully shifted.</p> |
| 883 | 978 |
| 884 <p>If the parser pops its stack until the stack is empty, and it still | 979 <p>If the parser pops its stack until the stack is empty, and it still |
| 885 is unable to shift the error symbol, then the %parse_failed routine | 980 is unable to shift the error symbol, then the %parse_failed routine |
| 886 is invoked and the parser resets itself to its start state, ready | 981 is invoked and the parser resets itself to its start state, ready |
| 887 to begin parsing a new file. This is what will happen at the very | 982 to begin parsing a new file. This is what will happen at the very |
| 888 first syntax error, of course, if there are no instances of the | 983 first syntax error, of course, if there are no instances of the |
| 889 ``error'' non-terminal in your grammar.</p> | 984 "error" non-terminal in your grammar.</p> |
| 890 | 985 |
| 891 </body> | 986 </body> |
| 892 </html> | 987 </html> |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2751253002:
[sql] Import SQLite 3.17.0. (Closed)
