Parse tree
parse tree is the graphical representation of symbol. It is a hierarchical structure which represents the derivation of the grammar to yield input string.
Root note of parse tree has the start symbol of the given grammar from where the derivation proceeds.
Leavs of parse tree represent terminals each interior note represents productions of grammar.
* If a -> XYZ is a production , then the parse tree there will have “A” as interior code whose children are x,y,z from its left to right .
Other definition ,
parse is that phase of compiler which takes token string as input and with the help of existing grammar,converts it into the corresponding parse tree . parser is also known as syntax analyzer .
Parse trees precedence
Parse tree follows the precedence of operator . The deepest sub tree traversed first. So the operator in the parent node has less precedence over the operator in the sub tree.
Parse tree follows these points :
l All leaf nodes have to be terminals.
l All interior nodes have to be non - terminals.
l In order traversal fives original input string
General Types of parser >>
1) universal parser
2) Top down parser
3) Bottom up parser
Universal parser :
>> can parse any kind of grammar.
>> Not very efficient
>> CYK algo, Earley’s algo.
Top down parser
the top down parsing is known as recursive parsing or predictive parsing bottom up parsing is used to construct a parse tree for an input string.
Bottom up parser
In the bottom up paring, the process starts with the input symbol and construct the parse tree up to the start symbol , by tracing out the rightmost derivation of string in reverse.
Important and related post :
Important and related post :
>> What is application software and system software
>> incremental model with details.
>> Software Engineering | Classification of Software Requirements
>>What is operating system
>>What is traffic monitoring system
>> what is computer virus and names of virus.
>>What is embedded control system
>> What is compiler .
>> What is linker.
>> What is Interpreter
>> Modern Principles Of Software Development
>> Types of Software Testing
>> Software Testing | Basics
>> Software Engineering | Debugging Approaches
>> Software Engineering | Classification of Software.
>> Deference between software engineering and computer science.
>> What is cost of software?.
>> which have been explicitly designed to support process iteration ?
>> Software engineering some question.
>> Deference between software engineering and computer science.
>> What is cost of software?.
>> which have been explicitly designed to support process iteration ?
>> Software engineering some question.
0 Comments