CS374: Programming Language Principles - Grammars

Activity Goals

The goals of this activity are:
  1. To describe a grammar in terms of tokens in BNF form
  2. To disambiguate a grammar

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity on the Class Activity Questions discussion board. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Chomsky Hierarchy of Languages

Chomsky-hierarchy
Grammar Languages Automaton Production rules (constraints)* Examples
Type-0 Recursively enumerable Turing machine {\displaystyle \gamma \rightarrow \alpha }
(no constraints)		 {\displaystyle L=\{w|w}
describes a terminating Turing machine
\}
Type-1 Context-sensitive Linear-bounded non-deterministic Turing machine \alpha A \beta \rightarrow \alpha \gamma \beta {\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}
Type-2 Context-free Non-deterministic pushdown automaton {\displaystyle A\rightarrow \alpha } {\displaystyle L=\{a^{n}b^{n}|n>0\}}
Type-3 Regular Finite state automaton {\displaystyle A\rightarrow {\text{a}}}
and
{\displaystyle A\rightarrow {\text{a}}B}		 {\displaystyle L=\{a^{n}|n\geq 0\}}

Questions

  1. What kind of language and machine would be used to balance parenthesis, and why?
  2. Why can't the context-free language be expressed with a regular language or finite state machine?
  3. What do you think is added to a finite state machine to create a push-down automata?

Model 2: Grammar Definition

Questions

  1. What does this language produce?
  2. How can this be modified to specify a language that accepts Strings of n a characters followed by n b characters?
  3. How might we parse a grammar? How can we make it easy to parse a grammar? For example, would it help if every production began with a unique terminal?

Model 3: Ambiguous Grammars

Questions

  1. How might selection-statement lead to a dangling else block ambiguity in a nested if statement?
  2. How is the ambiguity resolved using the open_statement instead?

Model 4: An Example Grammar with an Ambiguity

Questions

  1. What are two different ways in which the expression 8*9+5 can be parsed into a parse tree? What does each parse tree look like?
  2. Can the resulting computed values be different as a result of this ambiguity?
  3. How can we resolve this ambiguity?

Model 5: An Example Grammar without an Ambiguity

Questions

  1. How would the expression 8*9+5 be parsed into a parse tree? How about 5+8*9?
  2. Given an ambiguous grammar, is there an algorithm that can disambiguate it, or do we have to design against the ambiguity up front? Why or why not?

Submission

Submit your answers to the questions using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section.