Class 09: Context-Free and Context-Sensistive Grammars

Held Wednesday, September 17, 2002

Summary

Today we consider two kinds of grammars: Context-Free Grammars (CFGs) and Context-Sensitive Grammars.

Notes

• For the second week in a row, I'll remind you that Lab Attendance is Required!. Attendance includes showing up on time.
• I'd like to know who each of you is planning to work with on phase 1 of the project.
  • Are there any questions on that phase of the project?
• I checked with my wise colleagues, and they all agree that there is no particularly concise way to represent the language of strings of digits with no repeated digits.
• Quiz: When is lexing ambiguous in Pascal (other than the potential of including a minus sign as the leading value in a number)?
• I'll be showing up for Algorithms again today. You should be able to find me in the office before Algorithms.

Due

• Homework 1.

Overview

• Context-Free Grammars
• Parse Trees
• Context-Sensitive Grammars

Context-Free Grammars

• The most common form of BNF grammars used are the so-called context-free grammars.
• In context-free grammars, the left-hand-sides of productions are always single nonterminals.
• When parsing with context-free grammars, we can build parse trees that prove that the string is in the language.
  • The root of a parse tree is the start symbol
  • The leaves of a parse tree are the tokens of the string (in order)
  • Each node and its down edges correspond to a production.
• You can build the tree starting with the start symbol and working your way down, or starting with the tokens and working your way up.
• Can you write a context-free grammar for ``strings of a's and b's with equal numbers of a's and b's''?
  • Yes, I'll ask you for it next class.

Parse Trees

• As we learned last class, grammars describe languages.
• A string, s, in in L(G) if there exist a sequence of productions in L(G) that transform S to s.
• We also observed that there can be different sequences of productions that generate the same string.
  • Some of these sequences differ only in the choice of which nonterminal to expand first.
• To clarify derivations (and to make it clear that the process can work in either direction), we often draw parse trees, pictorial representations of derivations.
• Parse trees are easiest to draw for context-free grammars.
• At the root of the tree is S, the start symbol.
• At the leaves of the tree are terminals, which are read from left to right.
• Internal nodes are nonterminals.
• The children of an internal node are the symbols at the right-hand side of a production for the nonterminal.
• We can build trees in two ways: working up from the leaves or down from the root.
• Some examples may clarify this issue.

Detour: Context-Sensitive Grammars

• Are there times that you want more than just a nonterminal on the left hand side?
• Yes, but not many that occur naturally in programming language design.
• You use extra information on the left-hand-side to note that you should translate something differently depending on its context.
• Here's a simple one. If we have a rule of the form A : XYZ, we might limit or expand the translation of Y based on the translation of X or Z.
• Here's the start of something that says that you need to parenthesize an addition stuff following a multiplication

  ASSIGN Exp : ASSIGN NUM
  ASSIGN Exp : ASSIGN ID
  ASSIGN Exp : ASSIGN Exp ADDOP Exp
  ASSIGN Exp : ASSIGN Exp MULOP Exp
  ...
  MULOP Exp : MULOP NUM
  MULOP Exp : MULOP ID
  MULOP Exp : MULOP PAREN Exp ADDOP Exp PAREN
  ...
  

• For some cases, you can write the grammar in other ways.
• The theoreticians tell us that there are grammars of this form that cannot be converted to context-free grammars.
• Here's a more intersting one that relies on the powers of nondeterminism
• We start with a simple language in which you declare variables and then use them.

  Program : Declarations DONE Assignments END
  Declarations : Declaration SEP Declarations
  Declarations :
  Declaration : TYPE ID
  Assignments : Assignment SEP ASSIGNMENTS
  Assignments : 
  Assignment : ID EQUALS Exp
  ...
  

• Now, let's add in some rules that limit the identifiers used to those declared previously.

  Program : Declarations DONE Assignments END
  Declarations : Declaration SEP Declarations
  Declarations :
  Declaration : Declare ID
  Declare ID : TYPE ID Declared ID
  Declared ID1 Declared ID2 : Declared ID2 Declared ID1
  Declared ID DONE : DONE Declared ID
  Declared ID END : END
  Assignments : Assignment SEP ASSIGNMENTS
  Assignments : 
  Declared ID Assignment : ID EQUALS Declared ID Exp
  Declared ID Assignment : Assignment Declared ID
  ...