This java project is an implementation of some algorithms used in Formal Languages and Automatons
The program can clean a grammar by applying the following steps :
- removing non accessible axioms
- removing non productive axioms
- refactoring axioms matching pattern : X -> X | epsilon
- removing epsilon productions
Example
Parsed Grammar :
S -> a | AB | B | aB | C | bCdCeCa | I | K
A -> aCaaC | B | AD
B -> BA | ADB
C -> Ac | cA | c | epsilon | X
D -> Bd
E -> epsilon | H
F -> epsilon
G -> GA | AGD | F
H -> h
I -> i | j
K -> K | epsilon
Cleaned Grammar :
S -> a | C | bCdCeCa | I | bdea | bdeCa | bdCea | bdCeCa | bCdea | bCdeCa | bCdCea | epsilon
A -> aCaaC | aaa | aaaC | aCaa
C -> Ac | cA | c
I -> i | j
It is possible to put a grammar in CNF. Information about CNF here
Prerequisites : The grammar must be epsilon free
Example (Using the above cleaned grammar)
S -> a | YF | MF | NF | PF | QF | UF | VF | XF | AG | GA | c | i | j | epsilon
A -> KC | HF | IC | JH
C -> AG | GA | c
B -> b
D -> d
E -> e
F -> a
G -> c
H -> FF
I -> HF
J -> FC
K -> JH
L -> BD
M -> LE
N -> MC
O -> LC
P -> OE
Q -> PC
R -> BC
T -> RD
U -> TE
V -> UC
W -> TC
X -> WE
Y -> XC
TODO
You can determine whether a word can be generated with a grammar. Information about CYK here
Prerequisites : The grammar must be in CNF (and obviously epsilon free)
Example
Parsed Grammar :
S -> AB
A -> BB | a
B -> AB | b
CYK.isMember(aab) : true
CYK.isMember(aba) : false
This program is only compatible with JAVA 8 and upper
Florian Pradines [email protected]
- Greibach Normal Form
- Get the tree with the CYK algorithm