Construct a Non-Recursive Table Driven Parser
Please find attached the ll1.out file, readme, rules and week9b notes.
Please note, we are using linux to compile the program, for example “g++ fa.cpp -o test”
Instructions:
- Using the algorithm, the program must parse using LL(1).
- You may assume that there are only three non-terminals in G (S, A, B)
- You may assume that there are only two terminal letters in G (0, 1).
- Given the grammar rules in an input file, the program should generate LL(1) table and parse strings cinedfrom the user.
- Display the stack content and the remaining input string each time the stack changes.
- Display “Reject” (with a reason) or “Accept”.
Project Part B &LL(1) Parser
===========================================================
Parsing for LL(1) Grammars
===========================================================
Parsing does not have to be recursive descent.
In fact, if we could avoid coding each non-terminal, then the parser can be more portable between source languages. (with a generic driver)
Backtracking == back up and try another path.
In order for a parser with no backtracking to work,
– we cannot have infinite loops/recursion, and
– given a non-terminal A and the current input a,there must be a unique production rule from each non-terminal given the next terminal.
Thus, we must have applied
– Left Recursion Removal, and then
– Left Factoring already.
Then, only one token look ahead is needed. èLL(1) Parser can be built.
===================================================
Implementation of Non-Recursive Table Driven Parser
===================================================
Non-recursive table driven parser uses a STACK and a PARSING TABLE.
Input : input string of tokens followed by $
Stack : grammar symbols (terminals and non-terminals) on top of $
Parsing table:M[A,a] says which unique path (rule) to take
when A is top of stack and
a is the current input token from the scanner
(ERROR if there is no path)
The entry is a production rule (or its RHS) that would derive
“a” first from A.
e.g.
p1 S -> 0 S 0
p2 S -> 1 S 1
p3 S -> c
M[S,0] is p1’s rhs i.e. 0 S 0
M[S,1] is p2’s rhs i.e. 1 S 1
M[S,c] is c
e.g.left factoring
S -> a A B
A -> a A | a =>A -> a X X ->epsilon | A
B -> b B | b =>B -> b Y Y ->epsilon | B
M[S,a]= a A B
M[S,b]= none
M[A,a]= a X
M[A,b]= none
M[B,a]= none
M[B,b]= b Y
M[X,a]= A
M[X,b] = none
M[Y,a] = none
M[Y,b]= B
Start with S on the stack on top of $
1) If top of the stack is $ and the input is $, success. Halt.
2) If top of the stack (terminal) matches the input (from the scanner),
pop top of the stack, and
advance the input pointer.
(This corresponds to “match”)
3) If top of the stack is non-terminal,
pop it, then
look up the table with the non-terminal and the input
to get a production rule and push the RHS of the rule.
e.g. If it is A -> UVW then push W, push V, push U
(This corresponds to expanding the non-terminal)
##Inter1:* Is this the left most or the right most derivation?
Another Example:
p1 A -> a B
p2 B -> b C
p3 C -> c
Table a b c
A p1 – –
B – p2 –
C – – p3
Start with the start symbol of the stack.
Stack A
$
Input a b c $
M[A,a] gives p1 (rhs = a B)
Stack a
B
$
Input a b c $
a matches a -> pop a ; eat a
Stack B
$
Input b c $
M[B,b] gives p2 (rhs = b C)
Stack b
C
$
Input b c $
b matches b -> pop b ; eat b
Stack C
$
Input c $
M[C,c] gives p3 (rhs = c)
Stack c
$
Input c $
c matches c -> pop c ; eat c
Stack $
Input $
$ matches $ so stop and success.
Two types of syntax errors:
Match fails (the top of stack does not match the input)
The M entry is blank (no production rule is available)
If the input was
c b $
But the stack had x, ERROR (mismatch)
If the input was
c b $
M[A,c] = empty so it is ERROR (unexpected input found)
If the input was
a b c c$
then the stack becomes empty with just $
when another c is seen. ERROR
End of Parsing
Solution
// // Freelancer1.cpp // Koktol_Codotof // // Created by Ali Mashreghi on 2017-11-23. // Copyright © 2017 Ali Mashreghi. All rights reserved. // #include #include #include using namespace std; string all_symbols = “SAB01”; //3 rows (S A B) and 5 columns (S A B 0 1) string table[3][5]; intsymbol_to_int(char x){ for(int i = 0; i = 0; i–){ cout<< x[i] < 0) return x[int(x.size()) – 1]; else return ‘ ‘; } int main(){ ifstream in(“./rules.txt”); string line = “”; //reading rules char symbol; while(getline(in, line)){ stringstream get(line); //reading from this line get >> symbol; char non_terminal = symbol; string right_hand_side = “”; get >> symbol; char left_symbol_of_rule = symbol; right_hand_side += symbol; while(get >> symbol && symbol != ‘$’){ right_hand_side += symbol; } int row = symbol_to_int(non_terminal); int col = symbol_to_int(left_symbol_of_rule); table
[row]
[col] = right_hand_side; } for(int i = 0; i < 3; i++){ for(int j = 0; j < 5; j++){ cout<< “row ” <> input; //beging processing the input string stack; //left to right of this string is like bottom to top of a stack stack.push_back(‘S’); int cur = 0; // current char on input while(true){ print_stack_contents(stack); cout<< “current char is: ” << input[cur] < 0) cout<< “Failure – input too short” <
[row]
[col]; if(rule == “”){ cout<< “Error: no rule found for this step” <= 0; i–){ stack.push_back(rule[i]); } } } return 0; }