Multipass precedence analysis
This paper considers parsing of strictly non context free languages. The notion of a controlled grammar is used to define by an inductive process successively larger families of languages starting with the context free family. If \(L_0\) represents the context free family, then the construction yields an infinite chain \(L_0\subset L_1\subset L_2\subset \cdots\subset CS\) of proper extensions, all within the context sensitive family \(CS\). The algorithm of Wirth and Weber is then generalized to provide the hierarchy with a parsing algorithm for its simple precedence languages. lt is shown that for languages in \(L_k\), the algorithm introduced takes time \(O(kn)\) and requires linear space in addition to the space for the precedence matrices.
- A geometric hierarchy of languages
- A hierarchy between context-free and context-sensitive languages
- Control sets on linear grammars
- EULER: A generalization of ALGOL and its formal definition: Part 1
- scientific article; zbMATH DE number 3473266 (Why is no real title available?)
- On the nonexistence of a phrase structure grammar for ALGOL 60
- Optimization of LR(k) parsers
- Programmed Grammars and Classes of Formal Languages
This page was built for publication: Multipass precedence analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1393278)
