Introduction of Syntax analyzer, Introduction of ambiguity in Compiler Design
16 February, 2016
- This chapter is devoted to parsing methods that are typically used in compilers.
- The syntax of programming language constructs can be specified by CFG (Context free grammar)or BNF(Backus- Naur form) Notations.
- A grammar gives a precise , yet easy -to - understand, syntactic specification of a programming language.
- We have learnt how tokens generate in Lexical analyzer step.
- In this step, we will learn how can we create a parse tree.
- Through parse tree a complier can understand the structure of program. how it will pass the string etc.
- Parsing can be done by two methods and these two methods also have sub parts .
- So start leaning now What is Syntax Analyzer?
- In Top down Parsing , It will start from starting symbol and proceed to children.
- In Bottom up parsing, it will start from children and will proceed to start symbol.
- Its more powerful approach.
- In TDP , it used Left recursion while deriving the string.
- In TDP , when a variable contain more than one possibility it become difficult to choose the right production.
- Derive a string with more than two parser called Ambiguous grammar.
- Types of Top down parser:
- Recursive Decent parser(Backtracking)
- Non- recursive parser(LL(1))(No recursion) (Predictive Parsing)
Bottom Up parser divide into two parts(Shift Reduce parser) :
LR Parser:
- LR(0)
- SLR(1)
- CLR(1)
- LALR(1)
OPERATOR PRECEDENCE PARSER:- Ambiguous or Unambiguous grammar
Sometimes an ambiguous can be written to eliminate the ambiguity.