Multipass precedence analysis (Q1393278): Difference between revisions
From MaRDI portal
Latest revision as of 14:09, 12 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Multipass precedence analysis |
scientific article |
Statements
Multipass precedence analysis (English)
0 references
1974
0 references
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.
0 references