Grammars
********

Languages
=========

A language is a set of words, or sentences.

Operations on languages: concatenation, alternation, power, closure.

Other operations: intersection, left and right divisions.

A parser, a scanner, more generally, an accepter are finite representation of a language.

Formal Grammars
===============

Interesting languages are infinite.  Problem: representing an infinite language as a finite entity.

An alphabet, a string, concatenation of strings, power of a string, length of a string, a formal language.

A phrase structure grammar, or grammar, G is a quadruple (T, N, S, R), T a set of terminal symbols, N , N a set of non terminal symbols, S, the axiom is a non terminal, and R is a finite set of production rules.  The vocabulary, V is the union of N and T.

A rule has the form x -> y where X is a non empty string over V and Y is a string over V.

A proto-word is a word made of terminals and non terminals.

Derivations.

Parse trees.

Chomsky Hierarchy
=================

Type 0
     Unrestricted phrase structure grammars, Turing Machine.

Type 1
Context sensitive
     Linear bounded Turing Machine.  Lhs of the production rules must be shorter than rhs.  Each production is of the form

          alpha1 A alpha2 -> alpha1 beta alpha2

     where alpha1 and alpha2 are proto-words, A is a non terminal, and beta is a non empty proto-word, with one exception possible S -> epsilon where S must not appear in a rhs.

Type 2
Context free
     Lhs must be a single nonterminal.  Algebraic language.  Any context free grammar can be rewritten without using the empty string in the rhs.

Type 3
     Linear production rule: at most one non terminal in RHS.

     Right linear production rules: X -> aY, X -> a.  Right linear grammars: right linear rules plus X -> epsilon.  Left linear rules, left linear grammars.  Adding X -> Y is OK.

     What of grammars with right and left linear rules?  What of X -> aYb?

     Regular/rational languages, regular/rational expressions, finite state machines.

The inclusions are proper.

Some Grammars
=============

Producing {a^n b^n c^n | n >= 1} (From Salooma, ex. 2.1, p 11):

     N = {S, A, B}
     T = {a, b, c}
     S = S
     P = S   -> a b c
         S   -> a A b c
         A b -> b A
         A c -> B b c c
         b B -> B b
         a B -> a a A
         a B -> a a

Producing {a^n b^n c^n | n >= 1} (From Machines, Languages, and Computation, ex. 3.1, p. 63):

     S   -> A
     A   -> a A B C
     A   -> a b C
     C B -> B C
     b B -> b b
     b C -> b c
     c C -> c c

Producing {a^n b^n | n >= 1} (From Machines, Languages, and Computation, ex. 3.2, p. 63):

     S   -> A
     A   -> a A B C
     A   -> a b C
     C B -> B C
     b B -> b b
     b C -> b

can you find a simple grammar defining the same language?

See Salooma, ex. 2.5, p 14 for a grammar of {a^p | p prime}.

Declaration and uses in programming languages:

     L = { w c w | w in {0, 1}+ }

Regular Expressions
===================

Empty string

Symbol

Alternation

Concatenation

Kleene closure
Repetition

Finite Automata
---------------

DFA, NFA.

NFA: empty transition, multiple edges with the same label, multiple entry points.

Building a NFA corresponding to a regexp.

Determinization of NFAs.

Context-free Grammars
=====================

G grammar is context free if all the rules look like: A -> ALPHA, with A as not terminal and ALPHA is a proto-word.

Writing a C-like instruction sequence seems easy having ins and ; as terminals..

     S -> S; S
     S -> ins
     S ->

Find a grammar producing the following words:

     a := 1;
     b := a + (c := a + 3, c)

First thing to do is obviously introducing terminals.  In a computer science meaning terminals are not characters or data units, but of course lexical units. For the current grammar we choose id, num, +, (, ), :=and ;:

     id := num;
     id := id + (id := id + num, id)

The only thing to do is to make a simple grammar.

     S -> S ; S
     S -> id := E

     E -> id
     E -> num
     E -> E + E
     E -> (S , E)

Many different notations exist for grammars. First of them is the BNF, Backus-Naur Form.

From http://cui.unige.ch/db-research/Enseignement/analyseinfo/AboutBNF.html

     BNF is an acronym for "Backus Naur Form". John Backus and Peter Naur introduced for the first time a formal notation to describe the syntax of a given language (This was for the description of the ALGOL 60 programming language, see [Naur 60]).

     To be precise, most of BNF was introduced by Backus in a report presented at an earlier UNESCO conference on ALGOL 58.  Few read the report, but when Peter Naur read it he was surprised at some of the differences he found between his and Backus's interpretation of ALGOL 58. He decided that for the successor to ALGOL, all participants of the first design had come to recognize some weaknesses, should be given in a similar form so that all participants should be aware of what they were agreeing to.  He made a few modificiations that are almost universally used and drew up on his own the BNF for ALGOL 60 at the meeting where it was designed.  Depending on how you attribute presenting it to the world, it was either by Backus in 59 or Naur in 60. (For more details on this period of programming languages history, see the introduction to Backus's Turing award article in Communications of the ACM, Vol. 21, No. 8, august 1978. This note was suggested by William B. Clodius from Los Alamos Natl. Lab).

     Since then, almost every author of books on new programming languages used it to specify the syntax rules of the language. See [Jensen 74] and [Wirth 82] for examples.

Uses of := or ::= instead of our -> is the first difference. We uses the | of regular expresions, terminals are shown as this, or bold characters..

     S := S ; S
        | id := E

     E := id
        | num
        | E + E
        | ( S , E )

Show out a BNF for flotting point numbers

     F  := - FP
         | FP
     FP := Cs
         | Cs . Cs
     Cs := C
         | C Cs
     C  := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

  - Parenthesis to group (compel priorities)

  - ? the character is optional(zero or one time).

  - * the character can be repeated as many time as you want(zero or more).

  - + the character is not optional and can be repeated (1 or more)

Having such features help us to have more readable grammars, and eliminating recursion most of the time:

     F  := -? FP
     FP := Cs (. Cs)?
     Cs := C+
     C  := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

We can simplify even more:

     F  := -? C+ (. C+)?
     C  := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Some people use [A] for (A)? and {A} for (A)*.

Ambiguous Grammars
==================

     S := S , S | I

Is this an ambiguous grammar ? Yes it is: I; I; Ican be understood two different ways...It's an associativity problem; the same for instruction sequences.  How can we deal with this problem?

     S ::= S ; I |  I

left recursive, or

     S ::= I ; S |  I

right recursive.

Ambiguity in context-free grammar can arise in two different ways:

  - Some sentence has two different parse trees.

          S -> S a S
          S -> b

  - Some sentence has two structurally equivalent parse trees, but the inner nodes are different.

          A -> A a
          A -> B a
          A -> b
          B -> B a
          B -> b

For our little toy grammar :

     E ::= E' + E  or  E ::= E + E'

     E' ::= id
         |  num
         |  (S, E)

The two are OK for addition but subtraction?  1 - 2 - 3 is (1 - 2) - 3 or 1 - (2 - 3)?  The first one, of course, subtraction is left associative. Then use left recursion.

The simplest grammar for integer arithmetics:

     E ::= E * E
         | E + E
         | E - E
         | E / E
         | ( E )
         | num

it's ambigous

Think about 1 + 2 * 3 : sum of factors.To make it unambiguous we must give associativity and priority.First (), then * and /, then + and -.

     E ::= E + T
        |  E - T
        |  T

     T ::= T * F
         | T / F
         | F

     F ::= num
         | ( E )

This time it is not ambiguous, but it's the same language! Understanding that grammars are structurs discribing languages, but grammars are far more meaningfull: by inference many grammars exist describing the same language (in fact an infinity, but it's not important because human can't imagine exactly this concept...unless someone can count till infinity i'll continue thinking that;it is not a shame, we are able to think about many concept we can't catch up), good grammars, less good one (ambiguous is not good, i think you already understood that). The only thing to do is finding the good grammar matching what you need. That's why we will have much more interest in grammar properties than languages properties.