Multipass precedence analysis (Q1393278): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Optimization of LR(k) parsers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the nonexistence of a phrase structure grammar for ALGOL 60 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4057550 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A hierarchy between context-free and context-sensitive languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Control sets on linear grammars / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A geometric hierarchy of languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Programmed Grammars and Classes of Formal Languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: EULER: A generalization of ALGOL and its formal definition: Part 1 / rank | |||
Normal rank |
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