Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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

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 March 28, 2024)
Created February 3, 2010, Updated February 19, 2017