Formal Ambiguity-resolving Syntax Definition with Asserted Shift Reduce Sets

Authors

1 Department of Electrical and Computer Engineering,Shahid Beheshti University and School of Computer Science,the Institute for Research in Fundamental Science (IPM),Tehran, Iran

2 Department of Electrical and Computer Engineering,Shahid Beheshti University,Tehran, Iran

Abstract

There are parser generators that accept ambiguous context-free grammars, where ambiguities are resolved via disambiguation rules, with the outcome of smaller parse tables and more efficient parsers. However, the compiler writers are expected to develop compact ambiguous grammars and extract ambiguity-resolving information from the syntax and semantics of the language. The aforementioned tasks require considerable expertise, not often owned by casual compiler writers, or even expert programmers who are assigned a serious compiler-writing task, while programming language designers are, usually, capable of providing a concise and compact ambiguous description of the language that may include ambiguity-resolving information.In this paper, we aim to provide a powerful notation for syntax definition, which enables the language designer to assert some shift and reduce sets associated with each production rule of the possibly ambiguous grammar. These sets of language tokens guide the parser generator to resolve the parse table conflicts that are caused by the ambiguities in the grammar or by other sources. The practicality of the proposed asserted shift reduce notation is supported by several examples from the constructs of contemporary programming languages and is tested to work properly via developing a parser generator that constructs conflict-free LALR (1) parse tables.

Keywords

Scientia Iranica
Volume 20, Issue 6 - Serial Number 12
Transactions on Computer Science & Engineering and Electrical Engineering (D)
December 2013
Pages 1939-1952

Files

Share

How to cite

Statistics