Grammar

• Regular Expression Weakness

  • Nested comments /* /* */ */
  • Parenthesis and Braces () {} []
  • State machine needs memory

• context-free grammar (CFG)
• BNF (Backus-Naur Form) notation
• checks a given source program
• creates the parse tree
• Otherwise gives the error messages
• → , λ , |
• S → aA
• S → b

• You can use

  • -> instead of →

https://www.nltk.org/book/ch08.html

Simple Grammars

• I

  1. S → aSb
  2. S → b
  3. abb, aabbb, aaabbbb,

• II

  • S → (S)
  • S → a
  • a, (a), ((a))

• III

  • S → [A]
  • A → aS
  • A → λ
  • [], [a[]], [a[a[]]]

1. Writing grammar is harder than finding sentences of a grammar

   • 87
   • 78968 + (3334+43)
   • 78968 * (3334+43)
   • 78968 * (334+43)
   • 78968 * ((334+43) * 4)
   • 78968 * ((334+43)* 4)
   • (23 + 45) + 45
   • (23 + 45) + (45 * 443)
   • 2 * ((23 + 45) + (45 * 443))

Grammar of simpler calculator

1. It has just +, *, (, )
2. There is no priority
3. No unary operator (+)

4. Use paranthesis for more that one operator

   1. (2+3)+4
   2. 2+(4+3)
   3. (2+(4+3))+5
   4. (2*(4*3))*5

5. Terminals

6. INT (for simplicity we use token.type: i)

   1. (i+i)+i
   2. i+(i+i)
   3. (i+(i+i))+i
   4. (i*(i*i))*i

7. {'+', '*'}
8. {'(', ')'}
9. No need for naming operators, just using the symbol
10. Use recursion

1. Start Symbol (S)
2. S → A + A
3. S → A * A
4. S → A
5. A → (S)
6. A → i
7. Derivation Tree

Derivation Tree(I)

Derivation Tree(II)

Derivation Tree(III)