辅导context-free、讲解Java, C/C++程序、辅导JavaScript, Python语言

Part 1: Top Down Parsers

You have been given the following unambiguous context-free grammar for a subset of arithmetic expressions:

E → E + T | T

T → T * F | F

F → (E) | a

A) Implement a parser for this language, as a hand-coded recursive descent parser.

Also, you have been given the following parsing table as the appropriate tables for a predictive parser for a left factored version of the previous grammar.

E → ?T E′

E′ → ?+ T E′ | ε

T → ?F T′

T ′ → F T′ | ε

F →( E ) | a

B) Use the parsing table to implement a predictive parser (replace the a token with an INT token to make it a little more interesting).

You can either use JFlex/flex as a tokeniser, or write a simple tokeniser yourself. As a minimum, it should recognise valid strings and reject invalid ones. For additional credit, extend the parser to either print the parse tree, or evaluate expressions.

Part 2: Bottom-Up Parser

Consider the following expression grammar

E → E + T | E - T | T

T → T * F | T / F | F

F → (E) | INT | ID

Where INT and ID are integers and standard programming-language variable names respectively.Using JCup, bison or similar, implement a bottom up parser for this language.

You can either use JFlex/flex to generate a lexical analyser, or use the one you wrote yourself in part 1 (note that interfacing a hand-written lexer to the parser may be more complex than using flex).? Again, as a minimum your parser should accept valid and reject invalid strings, but you can add other features as you wish (printing parse tree, evaluating expressions, etc).

Please submit a jar, tar or ZIP archive of your source, together with some instructions on how to build your exercise.? You are free to use Java, C, C++, JavaScript, Python, Perl, Ruby or OCAML: for any other language, please check with me first.

Marking: For each part of the project, the marks will be given mainly for basic accept/reject functionality and for any additional functionality.

Further details/clarifications might be posted in the announcements section.?