Compiler Design Lab

---

Syntax Analysis/Parsing (LL(1) Predictive Parser)

Following are my details for assignment submission:

Name:     Sakshi Shashikant Yeole2

Roll No.:  20CS01047

Semester:  7th

Year of study:  4th year

Subject:   Compiler Design Laboratory

Assignment:  Assignment - 5

---

How to run

1. Clone the repository: https://github.com/SakshiYeole/Predictive_Parser.git
2. Open in your favourite editor. (The editor used while making this project is VS Code and also the path are currently coded to handle only windows)
3. Run the complete project by running the Grammar.py. Follow the prompt to give input.

Problem Statement

For each of the grammars, perform the following steps and implement a predictive LL(1) parser.

1. Transform the given grammar to LL(1).

   Details:

   Transform the grammar to LL(1) (without affecting/changing the language) by removal of left-recursion, and finding an equivalent left-factored Grammar. Write a LL(1) grammar in an output file.

2. Compute First and Follow Set.

   Details:

   For the LL(1) grammar obtained from step1, compute the FIRST set of all symbols and the FOLLOW set of all the non-terminalsymbols. Store this information in a separate file.

3. Compute the parse table.

   Details:

   Create a parsing table for the LL(1) using FIRST and FOLLOW set.

4. Take a string input and parse it using the parse table computed in step3.

Input Grammar Format

1. First line contains the start symbol.

2. Second line contains all the Non-terminal symbols in space separated manner.

3. Next Line contains all the Terminal symbols in space separated manner.

4. Next line till the end of file ontains production rules in format:

   P -> prog DL SL end | if else then

   The left hand side and right side separated by ->. The right hand side rules separated by '|'. And for each rule, the symbols also be space separated

   Example input grammar

   P

   AE BE D DL E F ES IOS IS NE P PE RE S SL T TY VL WS

   + - * / = < > ( ) { } := ; and else end ic id if int do fc float not or print prog scan str then while

   P -> prog DL SL end

   DL -> D DL | ε

   D -> TY VL ;

   TY -> int | float

   VL -> id VL | id

   SL -> S SL | ε

   S -> ES | IS | WS | IOS

   ES -> id := E ;

   IS -> if BE then SL end | if BE then SL else SL end

   WS -> while BE do SL end

   IOS -> print PE | scan id

   PE -> E | str

   BE -> BE or AE | AE

   AE -> AE and NE | NE

   NE -> not NE | { BE } | RE

   RE -> E = E | E < E | E > E

   E -> E + T | E - T | T

   T -> T * F | T / F | F

   F -> ( E ) | id | ic | fc

NOTE: The input grammar should be written here and the input text here.

Understanding the codebase

The project consists of many folders, lets walk through one after another.

1. Flex directory:

   The flex directory consists of all the files related to flex. Currently, there are two subdirectories, Grammar1 and Grammar2. In each of this directory, there is a file with ".l" extension. This is the lex file, which will be used for lexical analysis.

2. Input directory:

   This is the directory for input text file from which all the input is read. The files in this directory is, InputText.txt and InputGrammar.txt.

3. Output directory: (will be created on the go)

   This directory contains the output files, namely "FirstFollowSet.txt", "EquivalentLeftFactoredandRemovingLeftRecursionGrammar.txt", "InputGrammar.txt", "ParsingSteps.txt", and "ParsingTable.txt". The names are quite self explanatory.

4. Grammar.py file:

   This file contains all the source code.

Flow of working of the code

Check the Grammar.py file to understand the flow. Following are the steps:

1. Create empty output directory.
2. Take in the grammar choice which needs to be run, currently there are two grammar choices 1 and 2.
3. Read the text from InputText.txt and feed it the lex program.
4. Compile and run the flex program.
5. Take the input grammar from "InputGrammar.txt".
6. Print the input grammar to output file.
7. Transform the input grammar into LL(1) grammar by applying algorithm for producing an equivalent left factored grammar and removal of left recursion. Print the grammar to output file.
8. Compute the first and follow set, and print it to output file.
9. Read the list of tokens from flex program output file.
10. Create a parsing table for LL(1) grammar, and print it to output file.
11. Feed the tokens to parser, which parses using parsing table.
12. Write the steps of parser to output file.
13. Print corresponding output whether the input text is accepted by the grammar or not.

For more details check the pdf: "Question.pdf"

Future scope of this project

1. As the above written steps can be done in parallel manner, we can find a dependency graph for the above steps, and apply threading.
2. Currently, the program does not check if the grammar is LL(1) or not. (This can be done by checking if their exists more than one production rule in a cell of parsing table.)
3. Also, the program does not check for error in lexical analysis explicitly. It will print error while parsing, but we can analyse the tokens and comment on lexical analysis.
4. The lex program is now hardcoded explicitly, we can write a program which can create a "lex.l" , and then use it for lexical analysis.