2023-08-16

2023-08-16

DFA, RL, RE, RG

• Languages recognized by a DFA/NFA are known as Regular Language
• Grammar of a regular language is Regular Grammar
• Regular Expression represents all possible strings that can be generated by a RG

Disambiguitation

• Choose the token which has the Longest prefix
  • Suppose we have a lexeme for8
  • We have two production rules
    • $FOR \rightarrow for$
    • $ID \rightarrow [a-zA-Z_][a-zA-Z0-9_]*$
  • for8 has a matching prefix of 4 for rule 2 and 3 for rule 1
  • We choose ID to be the token of for8
• Rule priority. Choose the rule which is defined first
  • Suppose we have a lexeme for
  • Rules are
    • $FOR \rightarrow for$
    • $ID \rightarrow [a-zA-Z_][a-zA-Z0-9_]*$
  • for will match with both and have equal length prefix
  • We will use rule 1 as it is defined first
  • So FOR will be token of for

Chomsky’s hierarchy of Languages