LING 501, Fall 2004: Augmented grammars

Modified September 29, correcting the errors noted in class, so that G₃ is now able to generate the string abc, and the definition of L_xx is changed to include the empty string.

Modified September 25, making the previous version obsolete.

Definition

An augmented grammar is any grammar whose productions are augmented with conditions expressed using features. Features may be associated with any nonterminal symbol in a derivation. A feature associated with a nonterminal symbol is shown following that nonterminal separated from it by a ".", e.g. A.COUNT is the COUNT feature associated with the nonterminal A. When the value is included with the feature, the feature and its value are bracketed and the dot omitted, as in A[COUNT 1]. If no ambiguity arises, the feature name may be omitted, as in A[1]. The values of the features may be assigned by the application of a production (indicated by the assignment operator ":=" for 'is set equal to'), or they may be compared (checked) using a comparison operator such as "=".

Examples

An augmented context-free grammar for generating the strictly indexed language L_n³ = {aⁿbⁿcⁿ : n > 0}

Here are the productions of an augmented context-free grammar G₁ that generates the SIXL L_n³ = {aⁿbⁿcⁿ | n > 0}. Nonterminal symbols that occur more than once in a production are distinguished by indices. The nonterminal symbol to the left of the rewrite arrow "® " gets index 0 (e.g. A₀), and recurring nonterminals to the right of the arrow get indices 1, 2, ... from left to right, e.g. A₁. COUNT is an integer feature (a feature that takes integer values) of each of the nonterminal symbols in G₁.

• S ® A B C, where A.COUNT := S.COUNT, B.COUNT := S.COUNT, C.COUNT := S.COUNT
• A₀ ® a A₁, where A₁.COUNT := A₀.COUNT - 1
• B₀ ® b B₁, where B₁.COUNT := B₀.COUNT - 1
• C₀ ® c C₁, where C₁.COUNT := C₀.COUNT - 1
• A ® e, where A.COUNT = 0
• B ® e, where B.COUNT = 0
• C ® e, where C.COUNT = 0

An augmented context-free grammar for parsing L_n³

Here are the productions of a grammar G₂ that parses L_n³. A derivation with respect to a parsing grammar (parser) such as G₂, is constructed in reverse fashion from that of a generating grammar (generator) such as G₁. [Note that I do not call G₂ a generative grammar. I use the latter term, as Chomsky does, to refer to the class of parsers and generators of languages.] It starts with a terminal string, and each successive line is built up from the preceding line by replacing a substring by a nonterminal symbol together with its features in accordance with a production of the grammar. The derivation is terminated if the final line is a start symbol, and it's easy to see that the language parsed by G₂ is identical to the language generated by G₁, namely L_n³. Each equivalence class of derivations with respect to a parser can be represented as a tree. However, the structural descriptions associated with the members of L_n³ by G₂ are different from those associated with them by G₁. To distinguish the productions of a parser from those of a generator, I also reverse the direction of the production arrow.

• S ¬ A B C, where A.COUNT = B.COUNT = C.COUNT
• A₀ ¬ A₁ A₂, where A₀.COUNT := A₁.COUNT + A₂.COUNT
• B₀ ¬ B₁ B₂, where B₀.COUNT := B₁.COUNT + B₂.COUNT
• C₀ ¬ C₁ C₂, where C₀.COUNT := C₁.COUNT + C₂.COUNT
• A ¬ a, where A.COUNT := 1
• B ¬ b, where B.COUNT := 1
• C ¬ c, where C.COUNT := 1

Test yourself exercise 1

Write the productions of a parser that is structurally equivalent to the generator G₁. Click here for an answer.

An augmented regular grammar for generating L_n³

The generator G₁ makes use of an infinite set of start symbols {S[n]: n > 0}. The generator G₃, whose productions are listed below, makes use of the single start symbol A[0]. Note that G₃ is an augmented regular grammar. NEWCOUNT , like COUNT (but defined for nonterminal B only), is an integer feature.

• A₀ ® a A₁, where A₁.COUNT := A₀.COUNT + 1
• A ® b B, where B.COUNT := A.COUNT, B.NEWCOUNT := A.COUNT - 1
• B₀ ® b B₁, where B₁.COUNT := B₀.COUNT, B₁.NEWCOUNT := B₀.NEWCOUNT - 1
• B ® c C, where B.NEWCOUNT = 0, C.COUNT := B.COUNT - 1
• C₀ ® c C₁, where C₁.COUNT := C₀.COUNT - 1
• C ® e, where C.COUNT = 0

Test yourself exercise 2

Write augmented regulars parsers for L_n³, one that parses from right-to-left and one that parses from left-to-right. Click here for answers.

An augmented regular grammar for generating the SIXL L_xx = {xx : x Î (a | b)+}

Here are the productions of an augmented regular generator G₄ for the SIXL L_xx = {xx : x Î (a | b)*}. The nonterminals have a string feature (feature whose value is a string) STR. The start symbol is S[e].

• S₀ ® a S₁, where S₁.STR := "a"^S₀.STR
• S₀ ® b S₁, where S₁.STR := "b"^S₀.STR
• S ® T, where T.STR := S.STR
• T₀ ® a T₁, where T₁.STR := T₀.STR ^ "a^-1"
• T₀ ® b T₁, where T₁.STR := T₀.STR ^ "b^-1"
• T ® e, where T.STR = e

Test yourself exercise 3

Write the productions of a left-to right augmented regular parser for L_xx. Click here for an answer.