CS374: Programming Language Principles - Grammars
Activity GoalsThe goals of this activity are:
- To describe a grammar in terms of tokens in BNF form
Supplemental ReadingFeel free to visit these resources for supplemental background reading material.
DirectionsConsider 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, and compare with your group to prepare for our whole-class discussion. 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
|Grammar||Languages||Automaton||Production rules (constraints)*||Examples|
|Type-0||Recursively enumerable||Turing machine||
describes a terminating Turing machine
|Type-1||Context-sensitive||Linear-bounded non-deterministic Turing machine|
|Type-2||Context-free||Non-deterministic pushdown automaton|
|Type-3||Regular||Finite state automaton||
- What kind of language and machine would be used to balance parenthesis, and why?
- Why can't the context-free language be expressed with a regular language or finite state machine?
- What do you think is added to a finite state machine to create a push-down automata?
Model 2: Grammar Definition
- What does this language produce?
- How can this be modified to specify a language that accepts
na characters followed by
- 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?
- Modify the above grammar to match all sets of balanced parenthesis, for example: