Automatic Detection and Replacement of Syntactic Constructs Causing Shift/Reduce Conflicts

Published

February 3, 2010

Author(s)

Thomas R. Kramer

Abstract

An automatic parser builder has been constructed that builds parsers for subsets of the DMIS language. The parser builder reads an EBNF file and writes C++ classes, a YACC file, and a Lex file which are then processed in the usual manner to build a parser. The parsers that are built build a parse tree using the C++ classes while they parse. The EBNF for DMIS is written in natural terms so that natural C++ classes are generated. However, if translated directly into YACC, the natural EBNF leads to 22 shift/reduce conflicts that fall into six types of problematic construct. Unnatural EBNF replacements for all six types have been found that recognize the same language. The six types and their replacements are described in detail in this paper. The parser builder recognizes the problematic constructs and makes the replacements automatically before generating YACC. The YACC that is generated parses in terms of the unnatural constructs while building a parse tree in terms of the natural C++ classes. The problematic constructs may occur in any statement-based language that uses a minor separator such as a comma, so knowing how to recognize and replace them may be broadly useful.

Citation

Software: Practice and Experience

Volume

40

Pub Type

Journals

Download Paper

Local Download

Keywords

conflict, DMIS, EBNF, parse, shift/reduce, YACC

Citation

Kramer, T. (2010), Automatic Detection and Replacement of Syntactic Constructs Causing Shift/Reduce Conflicts, Software: Practice and Experience, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=824706 (Accessed December 26, 2024)