Formal parsing systems
Sheila A. Greibach · Communications of the ACM · 1964
Automatic syntactic analysis has recently become important for both natural language data processing and syntax-directed compilers. A formal parsing system G = ( V, μ, T, R ) consists of two finite disjoint vocabularies, V and T , a many-many map, μ , from V onto T , and a recursive set R of strings in T called syntactic sentence classes. Every program for automatic syntactic analysis determines a formal parsing system. A directed production analyzer ( I, T, X, ρ ) is a nondeterministic pushdown-store machine with internal vocabulary I , input vocabulary T , and all productions of ρ in the form: ( Z, a ) → aY 1 ··· Y m , Z, Y i ε I, a ε T . Every context-free language can be analyzed by a directed production analyzer.