CS4031 Assignment 02 - LL(1) Parser

Team Members

• Student 1 - 22i-1050
• Student 2 - 22i-1171

Language

Java

Project Structure

Assignment 2/
|-- build.bat
|-- README.md
|-- bin/
|-- docs/
|   |-- report_template.md
|   `-- report.tex
|-- input/
|   |-- g1_errors.txt
|   |-- g1_valid.txt
|   |-- g3_errors.txt
|   |-- g3_valid.txt
|   |-- g4_errors.txt
|   |-- g4_valid.txt
|   |-- grammar1.txt
|   |-- grammar2.txt
|   |-- grammar3.txt
|   |-- grammar4_indirect_left_recursion.txt
|   |-- input_edge_cases.txt
|   |-- input_errors.txt
|   `-- input_valid.txt
|-- output/
|   |-- first_follow_sets.txt
|   |-- grammar_transformed.txt
|   |-- parse_trees.txt
|   |-- parsing_table.txt
|   |-- parsing_trace1.txt
|   |-- parsing_trace2.txt
|   |-- grammar1/
|   |   |-- first_follow_sets.txt
|   |   |-- grammar_transformed.txt
|   |   |-- parse_trees.txt
|   |   |-- parsing_table.txt
|   |   |-- parsing_trace1.txt
|   |   `-- parsing_trace2.txt
|   |-- grammar2_edge/
|   |   |-- first_follow_sets.txt
|   |   |-- grammar_transformed.txt
|   |   |-- parse_trees.txt
|   |   |-- parsing_table.txt
|   |   |-- parsing_trace1.txt
|   |   `-- parsing_trace2.txt
|   |-- grammar3/
|   |   |-- first_follow_sets.txt
|   |   |-- grammar_transformed.txt
|   |   |-- parse_trees.txt
|   |   |-- parsing_table.txt
|   |   |-- parsing_trace1.txt
|   |   `-- parsing_trace2.txt
|   `-- grammar4/
|       |-- first_follow_sets.txt
|       |-- grammar_transformed.txt
|       |-- parse_trees.txt
|       |-- parsing_table.txt
|       |-- parsing_trace1.txt
|       `-- parsing_trace2.txt
`-- src/
	|-- ErrorHandler.java
	|-- FirstFollow.java
	|-- Grammar.java
	|-- Main.java
	|-- Parser.java
	|-- ParsingTable.java
	|-- Stack.java
	`-- Tree.java

Compilation Instructions

On Windows PowerShell:

javac -d bin src/*.java

Execution Instructions

Default run (uses input/grammar2.txt, input/input_valid.txt, input/input_errors.txt):

java -cp bin Main

Run with custom files:

java -cp bin Main <grammarFile> <validInputFile> <errorInputFile> <outputDir>

Example:

java -cp bin Main input/grammar1.txt input/input_valid.txt input/input_errors.txt output

Input File Format

• One input string per line.
• Tokens must be separated by spaces.
• Tokens must belong to grammar terminals.

Grammar File Format

• One production per line.
• Format: NonTerminal -> production1 | production2 | ...
• Use epsilon or @ for epsilon.
• Non-terminals must start with uppercase and have at least 2 characters.

Sample Grammar Files

• grammar1.txt: optional first symbol with epsilon
• grammar2.txt: arithmetic expression grammar
• grammar3.txt: dangling else grammar
• grammar4_indirect_left_recursion.txt: indirect left recursion test

Output Files

• output/grammar_transformed.txt
• output/first_follow_sets.txt
• output/parsing_table.txt
• output/parsing_trace1.txt
• output/parsing_trace2.txt
• output/parse_trees.txt

Known Limitations

• Grammar symbols are space-tokenized on RHS.
• Parse tree generation is provided for accepted strings only.
• Error recovery uses panic mode (skip input or pop non-terminal on FOLLOW sync).