辅导Java, C/C++、辅导JavaScript/Python编程语言、讲解Perl/Ruby/OCAML

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.?