parsingcontext-free-grammarfinite-automatacontext-free-languageautomata-theory

What means IO$,IF$,$ in CFG

Parse the expression: IF i> i THEN i = i + i * i using the following CFG definition of a small programming language,

S → ASSIGNMENT$| GOTO$| IF$| IO$
ASSIGNMENT$ → i = ALEX
GOTO$ → GOTO NUMBER
IF$ → IF CONDITION THEN S
    | IF CONDITION THEN S ELSE S
CONDITION → ALEX = ALEX| ALEX ≠ ALEX| ALEX > ALEX
          | CONDITION AND CONDITION
          | CONDITION OR CONDITION
          | NOT CONDITION
IO$ → READ i| PRINT i

HINTS:

  1. ALEX stands for algebraic expression
  2. the names end in $ are class
  3. the terminals are { = GOTO IF THEN ELSE ≠ > AND OR NOT READ PRINT }
  4. whatever terminals are introduced in the definitions of i, ALEX, and NUMBER.
Solution

  • It looks to me like '$' is an abbreviation for 'STATEMENT'. E.g., "IF$" means "IF STATEMENT".

    But regardless of what it "means", you can treat it as if it were an ordinary letter for the purpose of the exercise: "IF$" is just the name of a non-terminal that occurs in the grammar.