Grammar Use Stories

Development

e.g. of a grammar for a shell/CLI
  1. program = list of (statement '\n')
  2. enhance grammar to allow multiple statements on one line:
    program = list of line
    line = list of statement, separated by ';', followed by '\n'
  3. refactor grammar:
    program = list of statement, separated by ';' or '\n'

Left Factorisation

  1. X = (A B)* C | A B A D
  2. expand:
    X = C | A B (A B)* C | A B A D
  3. factorise:
    X = C | A B ( (A B)* C | A D )
  4. expand:
    X = C | A B ( C | A B (A B)* C | A D )
  5. factorise:
    X = C | A B ( C | A (B (A B)* C | D ) )
"unroll" means (A)* B -> (A A)* A? B
"expand" means A (B)* C -> A C | A (B)+ C or A C | A B (B)* C
This page is maintained by and copyright © Pete Jinks [last modified 21/April/2004] suggestions, corrections etc. welcome. You are welcome to make educational, not-for-profit use (else what would be the point!) but please give due credit.