Prezentacja programu PowerPoint

Classification of formal grammars

• Regular grammars

• Context free grammars

• Context sensitive grammars

• Unrestricted grammars

• Generalization / difficulty of parsing

Parsing methods

• Top-down parsing approach:
• LL parsers – Left to Right,
• Leftmost Derivation
• Bottom-up parsing approach
• LR parsers – Left to Right,
• Rightmost Derivation
• LALR parsers – Look Ahead LR
• (use of lookahead symbols
• to aid the parsing process)
• GLR parsers – Generalized LR
• (multiple parsing threads
• in order to resolve ambiguities)

Grammar of Simple Arithmetic Expressions

• V = {“a”, ”b”, ”d”, ”+”, ”*”, “(“, “)”}
•  = {E, C, F}
• E – expression
• C – component
• F – factor
•  = E
• P = {
• ::= | “+” | “+”
• ::= | “*” | “*”
• ::= “(“ “)” | “a” | “b” | “d”
• }

Grammar of Reverse Polish Notation

• V = {“a”, ”b”, ”d”, ”+”, ”*”}
•  = {W, Z, X, O}
•  = W
• P = {
• ::= |
• ::= |
• ::= “a” | “b” | “d”
• ::= “+” | “*”
• }

(a + b) * d  a b + d *  d a b + *

• “a”

• “b”

• “+”

• “*”

• “d”

Algorithm of finding the result of arithmetic expressions in RPN

• START

• Parameter

• No

• Yes

• Read a symbol
• (from the left to the right)

• Put the parameter
• on the top of the stack

• Operator

• Yes

• Get parameters
• from the stack,
• execute the operation,
• put the result
• on the top of the stack

• 

• END

• ERROR

• No

• No

• Yes

• 2, 3, 4, 5, +, *, +,

Input	Stack
2	2
3	2, 3
4	2, 3, 4
5	2, 3, 4, 5
+	2, 3, 9
*	2, 27
+	29
