Parser generation and grammar manipulation using prolog's infinite trees
✍ Scribed by Francis Giannesini; Jacques Cohen
- Publisher
- Elsevier Science
- Year
- 1984
- Tongue
- English
- Weight
- 825 KB
- Volume
- 1
- Category
- Article
- ISSN
- 0743-1066
No coin nor oath required. For personal study only.
✦ Synopsis
The construction of parsers recognizing strings in a context-free language L(G) is usually done by generating a set of PROLOG clauses capable of parsing strings of L. Although this is a convenient way of generating parsers, it does not readily allow one to study the properties of G or to perform grammar transformations. This paper proposes a general PROLOG parser capable of analyzing the strings of L(G) when G is presented as an infinite tree. In particular, if the syntax of the grammar rules themselves is specified by a grammar, the parser can be used to recognize context-free grammar rules. Subsequently, actions can be attached to the parser so that it is possible to generate infinite trees for any grammar G'. Strings of L(G') can then be analyzed uing the same general parser. The proposed approach allows the verification of conditions such as left recursion, satisfiability of LL(l) requirements, as well as grammar transformations such as E elimination. The same analyzer is also capable of generating efficient parsers for specific machines. a + Research partly support by NSF grant DCR 83-17892.