Recursive descent parser generator: Difference between revisions
Content added Content deleted
mNo edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
Write a recursive descent parser generator that takes |
Write a recursive descent parser generator that takes a description of a grammar as input and outputs the source code for a parser in the same language as the generator. (So a generator written in C++ would output C++ source code for the parser.) You can assume that all of the rules have been preprocessed into a form suitable for the construction of a recursive descent parser. See here for more details: http://www.cs.engr.uky.edu/~lewis/essays/compilers/rec-des.html |
||
Example grammar: |
|||
Input format: |
|||
<pre> |
<pre> |
||
plus \+ |
|||
times \* |
|||
var [a-z]+ |
var [a-z]+ |
||
!! start -> expr start2 |
|||
... |
|||
!! start2 -> plus start2 |
|||
!! start2 -> expr |
|||
!! expr -> var expr2 |
|||
!! expr2 -> times expr2 |
|||
!! expr2 -> var |
|||
</pre> |
</pre> |
||
Use the parser generator to build a parser that takes arithmetic expressions and turns them in to three address code. The resulting parser should take this (or something similar) as input: |
|||
The first section contains the token definitions. Each line contains the name of a token followed by a regular expression. If your language does not have support for regular expressions, you can use something simpler, but make a note of the details. Tokens are to be matched greedily in the order given. The token section ends with a blank line. |
|||
<pre> |
|||
(one + two) * three - four * five |
|||
123 + 321 |
|||
</pre> |
|||
And generate this (or something similar) as output: |
|||
The second section contains the production rules. Each rule consists of a non-terminal symbol and [more work needs to be done on this part of the task]. You can assume that all of the rules have been preprocessed into a form suitable for the construction of a recursive descent parser. See here for more details: http://www.cs.engr.uky.edu/~lewis/essays/compilers/rec-des.html |
|||
<pre> |
|||
_0001 = one + two |
|||
_0002 = _0001 * three |
|||
_0003 = four * five |
|||
_0004 = _0002 - _0003 |
|||
_0005 = 123 + 321 |
|||
</pre> |
|||
Revision as of 20:30, 2 April 2014
Recursive descent parser generator is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Write a recursive descent parser generator that takes a description of a grammar as input and outputs the source code for a parser in the same language as the generator. (So a generator written in C++ would output C++ source code for the parser.) You can assume that all of the rules have been preprocessed into a form suitable for the construction of a recursive descent parser. See here for more details: http://www.cs.engr.uky.edu/~lewis/essays/compilers/rec-des.html
Example grammar:
plus \+ times \* var [a-z]+ !! start -> expr start2 !! start2 -> plus start2 !! start2 -> expr !! expr -> var expr2 !! expr2 -> times expr2 !! expr2 -> var
Use the parser generator to build a parser that takes arithmetic expressions and turns them in to three address code. The resulting parser should take this (or something similar) as input:
(one + two) * three - four * five 123 + 321
And generate this (or something similar) as output:
_0001 = one + two _0002 = _0001 * three _0003 = four * five _0004 = _0002 - _0003 _0005 = 123 + 321