Program a simple Syntax Analyzer.
- Input1: Stream of characters
- Assume that they are given in the file "./sample/Input.txt"
- Input2: Context-Free Grammar
Assume that they are defined in the file "./sample/Language.txt"
Also, additonal priority relationships are defined in the file "./sample/Priority.txt"
- Output: Sequence of reductions
- The result is displayed in the file โ./sample/Analysis Result.txtโ
I have implemented a canonical LR(1) Parser using Soft Coding:
- User can customize the productions being used by modified file "./sample/Language.txt". following the pattern "Production
$(items in productions, seperated by space)$ ".- User can change the priority of the terminals.
- Program constructs a "Production" object for each production.
- Program merges the objects and finally constructs a "Language" object.
- Program generates a LR_DFA for the "Language" object.
- Program constructs a LR_Parser which includes a LR_DFA
- Program calls the LR_Parser's "parseLine" method for dealing with a line of input sequence.
- Program displays an analysis result for each input sequence.
The basic assumptions are given as follow:
- There are not any "shift-shift" conflicts and "reduce-reduce" conflicts for constructing a parsing table (even though the LR parsing table is not explicitly given).
- The production whose id is 0 should contain an augmented-grammar starting label (i.e. S'), and any other productions should not include the starting label as a component in its right handside part.
- Computing "first": referring to Dragon Book 4.4.2. ("first" method in file "Language.hpp")
- Computing "clousure": referring to Dragon Book Algorithm 4.53. ("clousure" method in file "LR_DFA.hpp")
- Constructing "LR_DFA": referring to Dragon Book Algorithm 4.53. ("construct" method in file "LR_DFA.hpp")
- Parsing: referring to Dragon Book Figure 4-36. ("parseLine" method in file "LR_Parser.hpp")
Q1: How to deal with ambiguity in an LR grammar? (For example, the "dangling else" problem)
A1: I use a terminal label stack ("terminal_stack" in "parseLine" method) to store previously appearing terminal labels. When constructing a LR_DFA, the program will maintain those cores where potential conflicts will occur. And when parsing a sequence, the program will first find out the outing edges, then get all possible actions(a shift, a reduce or a shift and a reduce), then:
If a terminal label "a" corresponds to action "SHIFT" and the prority of label "a" is higher than the terminal label "b" which is the top element in terminal_stack, then the current action should be modified to "SHIFT".
Q2: Is the LR paring table indispensable for my LR parser?
A2: Not exactly. Program can be run merely based on previously constructed LR_DFA, because it contains all the information needed in parsing(like the label corresponding to an action, the next state for shifiting, and so on).
See the files in directory "sample".