Back القواعد الغامضة Arabic Nejednoznačna gramatika BS Nejednoznačná gramatika Czech Mehrdeutige Grammatik German Gramática ambigua Spanish دستور زبان مبهم Persian Grammaire ambigüe French Nejednoznačna gramatika Croatian Grammatica ambigua Italian 曖昧な文法 Japanese

Ambiguous grammar

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree.[1] Every non-empty context-free language admits an ambiguous grammar by introducing e.g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

For computer programming languages, the reference grammar is often ambiguous, due to issues such as the dangling else problem. If present, these ambiguities are generally resolved by adding precedence rules or other context-sensitive parsing rules, so the overall phrase grammar is unambiguous.[citation needed] Some parsing algorithms (such as Earley[2] or GLR parsers) can generate sets of parse trees (or "parse forests") from strings that are syntactically ambiguous.[3]

  1. ^ Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. ISBN 978-90-272-3250-2.
  2. ^ Scott, Elizabeth (April 1, 2008). "SPPF-Style Parsing From Earley Recognizers". Electronic Notes in Theoretical Computer Science. 203 (2): 53–67. doi:10.1016/j.entcs.2008.03.044.
  3. ^ Tomita, Masaru. "An efficient augmented-context-free parsing algorithm." Computational linguistics 13.1-2 (1987): 31-46.

Developed by StudentB