TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Automata Ambiguity in Grammar

Automata Ambiguity in Grammar with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

<< Back to AUTOMATA

Ambiguity in Grammar

A grammar is said to be ambiguous if there exists more than one leftmost derivation or more than one rightmost derivation or more than one parse tree for the given input string. If the grammar is not ambiguous, then it is called unambiguous.

If the grammar has ambiguity, then it is not good for compiler construction. No method can automatically detect and remove the ambiguity, but we can remove ambiguity by re-writing the whole grammar without ambiguity.

Example 1:

Let us consider a grammar G with the production rule

E → I
E → E + E
E → E * E
E → (E)
I → ε | 0 | 1 | 2 | ... | 9

Solution:

For the string "3 * 2 + 5", the above grammar can generate two parse trees by leftmost derivation:

Ambiguity in Grammar

Since there are two parse trees for a single string "3 * 2 + 5", the grammar G is ambiguous.

Example 2:

Check whether the given grammar G is ambiguous or not.

E → E + E
E → E - E
E → id

Solution:

From the above grammar String "id + id - id" can be derived in 2 ways:

First Leftmost derivation

E → E + E
   → id + E
   → id + E - E
   → id + id - E
   → id + id- id

Second Leftmost derivation

E → E - E
   → E + E - E
   → id + E - E
   → id + id - E
   → id + id - id

Since there are two leftmost derivation for a single string "id + id - id", the grammar G is ambiguous.

Example 3:

Check whether the given grammar G is ambiguous or not.

S → aSb | SS
S → ε

Solution:

For the string "aabb" the above grammar can generate two parse trees

Ambiguity in Grammar

Since there are two parse trees for a single string "aabb", the grammar G is ambiguous.

Example 4:

Check whether the given grammar G is ambiguous or not.

A → AA
A → (A)
A → a

Solution:

For the string "a(a)aa" the above grammar can generate two parse trees:

Ambiguity in Grammar

Since there are two parse trees for a single string "a(a)aa", the grammar G is ambiguous.






Related Links:


Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf