Title: Deterministic parsing of languages with dynamic operators
Abstract: Allowing the programmer to dene operators in a language makes for more readable code but also complicates the job of parsing; standard parsing techniques cannot accommodate dynamic grammars. We present an LR parsing methodology, called deferred decision parsing, that handles dynamic operator declarations, that is, operators that are declared at run time, are applicable only within a program or context, and are not in the underlying language or grammar. It uses a parser generator that takes production rules as input, and generates a table-driven LR parser, much like yacc. Shift/reduce conicts that involve dynamic operators are resolved at parse time rather than at table construction time. For an operator-rich language, this technique reduces the size of the grammar needed and parse table produced. The added cost to the parser is minimal. Ambiguous operator constructs can either be detected by the parser as input is being read or avoided altogether by enforcing reasonable restrictions on operator declarations. We have been able to describe the syntax of Prolog, a language known for its liberal use of operators, and Standard ML, which supports local declarations of operators. Denite clause grammars (DCGs), a novel parsing feature of Prolog, can be translated into ecien t code by our parser generator. The implementation has the advantage that the Originally appeared in \Logic Programming | Proceedings of the 1993 International Symposium (ILPS93)
Publication Year: 1993
Publication Date: 1993-12-01
Language: en
Type: article
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot