Faster ambiguity detection by grammar filtering

H.J.S. Basten; J.J. Vinju

doi:10.1145/1868281.1868286

Faster ambiguity detection by grammar filtering

H.J.S. Basten, J.J. Vinju

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

12 Citations (Scopus)

Abstract

Real programming languages are often defined using ambiguous context-free grammars. Some ambiguity is intentional while other ambiguity is accidental. A good grammar development environment should therefore contain a static ambiguity checker to help the grammar engineer. Ambiguity of context-free grammars is an undecidable property. Nevertheless, various imperfect ambiguity checkers exist. Exhaustive methods are accurate, but suffer from non-termination. Termination is guaranteed by approximative methods, at the expense of accuracy. In this paper we combine an approximative method with an exhaustive method. We present an extension to the Noncanonical Unambiguity Test that identifies production rules that do not contribute to the ambiguity of a grammar and show how this information can be used to significantly reduce the search space of exhaustive methods. Our experimental evaluation on a number of real world grammars shows orders of magnitude gains in efficiency in some cases and negligible losses of efficiency in others.

Original language	English
Title of host publication	Proceedings of the Tenth Workshop on Language Descriptions, Tools and Applications (LDTA'10), March 28-29, 2010, Paphos, Cyprus
Editors	C. Braband, P.-E. Morfeau
Place of Publication	New York NY
Publisher	Association for Computing Machinery, Inc
Pages	5/1-9
ISBN (Print)	978-1-4503-0063-6
DOIs	https://doi.org/10.1145/1868281.1868286
Publication status	Published - 2010
Event	10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010) - Paphos, Greece Duration: 27 Mar 2010 → 28 Mar 2010 Conference number: 10 http://ldta.info/2010/

Workshop

Workshop	10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010)
Abbreviated title	LDTA 2010
Country/Territory	Greece
City	Paphos
Period	27/03/10 → 28/03/10
Other	Workshop held as a satellite event of the 13th European Joint Conferences on Theory and Practice of Software (ETAPS 2010)
Internet address	http://ldta.info/2010/

Access to Document

10.1145/1868281.1868286

Cite this

@inproceedings{edb129c268c746009464b84f04b63f69,

title = "Faster ambiguity detection by grammar filtering",

abstract = "Real programming languages are often defined using ambiguous context-free grammars. Some ambiguity is intentional while other ambiguity is accidental. A good grammar development environment should therefore contain a static ambiguity checker to help the grammar engineer. Ambiguity of context-free grammars is an undecidable property. Nevertheless, various imperfect ambiguity checkers exist. Exhaustive methods are accurate, but suffer from non-termination. Termination is guaranteed by approximative methods, at the expense of accuracy. In this paper we combine an approximative method with an exhaustive method. We present an extension to the Noncanonical Unambiguity Test that identifies production rules that do not contribute to the ambiguity of a grammar and show how this information can be used to significantly reduce the search space of exhaustive methods. Our experimental evaluation on a number of real world grammars shows orders of magnitude gains in efficiency in some cases and negligible losses of efficiency in others.",

author = "H.J.S. Basten and J.J. Vinju",

year = "2010",

doi = "10.1145/1868281.1868286",

language = "English",

isbn = "978-1-4503-0063-6",

pages = "5/1--9",

editor = "C. Braband and P.-E. Morfeau",

booktitle = "Proceedings of the Tenth Workshop on Language Descriptions, Tools and Applications (LDTA'10), March 28-29, 2010, Paphos, Cyprus",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

note = "10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010), LDTA 2010 ; Conference date: 27-03-2010 Through 28-03-2010",

url = "http://ldta.info/2010/",

}

Basten, HJS & Vinju, JJ 2010, Faster ambiguity detection by grammar filtering. in C Braband & P-E Morfeau (eds), Proceedings of the Tenth Workshop on Language Descriptions, Tools and Applications (LDTA'10), March 28-29, 2010, Paphos, Cyprus. Association for Computing Machinery, Inc, New York NY, pp. 5/1-9, 10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010), Paphos, Greece, 27/03/10. https://doi.org/10.1145/1868281.1868286

Faster ambiguity detection by grammar filtering. / Basten, H.J.S.; Vinju, J.J.
Proceedings of the Tenth Workshop on Language Descriptions, Tools and Applications (LDTA'10), March 28-29, 2010, Paphos, Cyprus. ed. / C. Braband; P.-E. Morfeau. New York NY: Association for Computing Machinery, Inc, 2010. p. 5/1-9.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Faster ambiguity detection by grammar filtering

AU - Basten, H.J.S.

AU - Vinju, J.J.

N1 - Conference code: 10

PY - 2010

Y1 - 2010

N2 - Real programming languages are often defined using ambiguous context-free grammars. Some ambiguity is intentional while other ambiguity is accidental. A good grammar development environment should therefore contain a static ambiguity checker to help the grammar engineer. Ambiguity of context-free grammars is an undecidable property. Nevertheless, various imperfect ambiguity checkers exist. Exhaustive methods are accurate, but suffer from non-termination. Termination is guaranteed by approximative methods, at the expense of accuracy. In this paper we combine an approximative method with an exhaustive method. We present an extension to the Noncanonical Unambiguity Test that identifies production rules that do not contribute to the ambiguity of a grammar and show how this information can be used to significantly reduce the search space of exhaustive methods. Our experimental evaluation on a number of real world grammars shows orders of magnitude gains in efficiency in some cases and negligible losses of efficiency in others.

AB - Real programming languages are often defined using ambiguous context-free grammars. Some ambiguity is intentional while other ambiguity is accidental. A good grammar development environment should therefore contain a static ambiguity checker to help the grammar engineer. Ambiguity of context-free grammars is an undecidable property. Nevertheless, various imperfect ambiguity checkers exist. Exhaustive methods are accurate, but suffer from non-termination. Termination is guaranteed by approximative methods, at the expense of accuracy. In this paper we combine an approximative method with an exhaustive method. We present an extension to the Noncanonical Unambiguity Test that identifies production rules that do not contribute to the ambiguity of a grammar and show how this information can be used to significantly reduce the search space of exhaustive methods. Our experimental evaluation on a number of real world grammars shows orders of magnitude gains in efficiency in some cases and negligible losses of efficiency in others.

U2 - 10.1145/1868281.1868286

DO - 10.1145/1868281.1868286

M3 - Conference contribution

SN - 978-1-4503-0063-6

SP - 5/1-9

BT - Proceedings of the Tenth Workshop on Language Descriptions, Tools and Applications (LDTA'10), March 28-29, 2010, Paphos, Cyprus

A2 - Braband, C.

A2 - Morfeau, P.-E.

PB - Association for Computing Machinery, Inc

CY - New York NY

T2 - 10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010)

Y2 - 27 March 2010 through 28 March 2010

ER -

Faster ambiguity detection by grammar filtering

Abstract

Workshop

Access to Document

Fingerprint

Cite this