# grammars

## https://zoo.cs.yale.edu/classes/cs201/topics/topic-cfls.pdf

P = # palindromes
| 
| 'a'
| 'b'
| 'a' P. 'a'
| 'b' P. 'b'
;

# http://infolab.stanford.edu/~ullman/ialc/spr10/slides/cfl1.pdf

B = # balanced
| B. B.
| '(' B. ')'
| '(' ')' # why not epsilon ?
;

S =
| 
| '(' S. ')' S.
;



#
# the bane, epsilon
# ( 2024-10-11 )
#
# ε •
#
# .. so epsilon is the bane of grammars..
# and rules can be rewritten equivalently,
# to expand `?` and `*` into distinct options;
# so can operations be reversed ? to collapse
# epsilon options directly into the parent rules /options ?
#
# ..

S1 =| A1 B1 'z' ;
A1 = # A1?
| 
| 'a'
;
B1 = # B1*
| 
| 'b' B1.
;

# S1 is not epsilon, but A and B are but do not need to be

# XXX what is the mechanical translation of `B` ???
# only removing the epsilon option would leave `B =| 'b' B. ;`
# which would be a problem, b/c B would be infinite...
# hmm.. wrong:
# removing the epsilon option propogates to *all* usages of `B`,
# including `B` itself; so the result would be `B =| 'b' B? ;`

S2 =| A2? B2? 'z' ;
A2 =| 'a' ;
B2 =| 'b' B2? ;
#B2 = 
#| 'b'
#| 'b' B2.
#;

# S2 is not epsilon, nor are A nor B



# .. okay.. more complicated test

X =| Y. ;
Y =
| # epsilon
| 'y' Z.
;
Z =
| W? # epsilon
| 'z' Y.
;
W =
| 'w'
| Y. Z. # epsilon
;

# .. Y is simple to propogate
# Z is more complicated
# W is .. a high-level issue
# .. begin with Y

X =| Y? ;
Y =| 'y' Z. ;
Z =
| W?
| 'z' Y?
;
W =
| 'w'
| Y? Z.
;

# Y is no-longer epsilon,
# other rules are functionally equivalent.
# continue with Z

X =| Y? ;
Y =| 'y' Z? ;
Z =
| W.
| 'z' Y?
;
W =
| 'w'
| Y? Z? # epsilon
;

# Z is now non-epsilon, all-else-equal
# .. how to handle W ? ..
# .. it's actually .. there are multiple correct solutions
# both Y and Z are optional; either can be made non-optional
# to make the option non-epsilon

# first attempt with Y
# ( i think Y will work, but Z will have issues )

X =| Y? ; # epsilon, but origin /start rule
Y =| 'y' Z? ;
Z =
| W? # epsilon
| 'z' Y?
;
W =
| 'w'
| Y. Z?
;

# .. now Z again .. no change, other than making the Z-option non-epsilon

X =| Y? ; # epsilon, but origin /start rule
Y =| 'y' Z? ;
Z =
| W.
| 'z' Y?
;
W =
| 'w'
| Y. Z?
;

# .. Y, Z, & W are non-epsilon;
# X is epsilon, but as the origin, cannot change that equivalently.
# .. success .. huh. cool

# okay, now beginning with Z

X =| Y? ;
Y =| 'y' Z? ;
Z =
| W.
| 'z' Y?
;
W =
| 'w'
| Y? Z? # epsilon
;

# XXX picking Z to make non-optional fails;
# it promotes to W becoming optional,
# which makes Z epsilon again; which to fix,
# promotes to Z becoming optional again..
# loop.

###

X =| Y. ;
Y = | | 'y' Z. ;
Z = | W? | 'z' Y. ;
W = | 'w' | Y. Z. ;

###

X =| Y? ;
Y =| 'y' Z? ;
Z = | W. | 'z' Y? ;
W = | 'w' | Y. Z? ;

# ""
# "y"
# "yw"
# "yyw"
# "yz"
# "yzy"
# "yzyywz"

# .. okay..
# so combining epsilon-collapsing & first-set analysis..
# what does that give ?
# non-epsilon options gives definitive first-sets

# ( also note: whitespace is a good example of a rule that is desirable to have as epsilon )
# ( would rather not have to postfix it everywhere as optional.. )



# http://david.tribble.com/text/lrk_parsing.html

#    Terminal Symbols # t1. num # t2. '(' # t3. ')' # t4. '+'
# Nonterminal Symbols # n1. Expr # n2. Factor
# Rules
# r1. Expr :   Factor
# r2. Expr :   '(' Expr ')'
# r3. Factor : num
# r4. Factor : '+' Factor
# r5. Factor : Factor '+' num

E =
| F
| '(' E. ')'
;
F =
| 'n'
| '+' F.
| F. '+' 'n'
;



( 2025-01-22 )

# expr
E =
| L.
| '(' S. ')'
;
# sum
S =
| P.
| S. '+' P.
| S. '-' P.
;
# product
P =
| E.
| P. '*' E.
| P. '/' E.
;
# (signed) literal
L =
| N.
| '+' N.
| '-' N.
;
# number
N =| '0' | '1' | '2' | '3' ;