Multipass precedence analysis (Q1393278): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:12, 5 March 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