Recognition and Parsing 
of Context-Free Languages

by

Jaime Rangel-Mondragón
jrangel@sunserver.uaq.mx

FACULTAD DE INFORMÁTICA
UNIVERSIDAD AUTÓNOMA DE QUERÉTARO
DIVISIÓN DE ESTUDIOS DE POSGRADO
Centro Universitario
Cerro de las Campanas s/n
C.P.76010 Querétaro, Qro.
Mexico


Copyright © October 1999, UAQ, Facultad de Informática

Permission is hereby granted to reproduce part or all of this file for any
 purpose other than direct profit providing that the source is acknowledged.

REFERENCES:	

Introduction to Formal Language Theory
M. Harrison
Addison-Wesley

Introduction to Automata, Languages andComputation
J. E. Hopcroft, J. D. Ullman
Addison-Wesley

Introduction to Computer Theory
D. I. A. Cohen
John Wiley & Sons

The Theory of Parsing, Translation and Compiling, Vol. I : Parsing
A. V. Aho, J. D. Ullman
Prentice Hall

A context-free grammar (CFG) is denoted by a 4-tuple (V, T, P, S), where V and T are disjoint finite sets of variables and terminals, respectively.  P is a finite set of productions of the form A -> α, where A ϵ V and α ϵ (V ⋃ T)* and S ϵ V is a special symbol called the start symbol. The language generated by a given CFG G is defined as L(G)={ω | ω ϵ T* and S \(TraditionalForm\`\(⟹\&*\)\) ω} where \(TraditionalForm\`\(⟹\&*\)\) is the reflexive and transitive closure of ->.

In this work we provide functions to manipulate the language generated by a given CFG G and solve the problem of recognition, i.e., to find out whether a given word ω ϵ L(G), and the problem of parsing a word that has been recognised, i.e., to find the actual chain of derivations giving rise to ω.. We denote the empty word by ε.

Variables will be represented by upper-case letters and terminals by lower-case letters. A CFG will be represented by a list of productions {A, α}, that is, CFG are of type {{_String,_String}..}.

Examples will follow each of the functions comprising this work.

We begin by designing functions to aliviate the input of CFG to be able to use the Backus-Naur form.

\(dissect[w_] := 
      Module[{p = \ StringPosition[w, "|"], ans = {}, i = 1}, 
		
        If[p == {}, {w}, 
			p = First\ /@\ p; 
			
          Map[\((AppendTo[ans, StringTake[w, {i, # - 1}]]; 
					
                i = # + 1)\)&, p]; 
			
          Append[ans, StringTake[w, {i, StringLength[w]}]]]]\)

dissect["ABC|DEF|a|ε|k|UV"]

\(BNF[G_] := 
      Module[{A, s, ans = {}}, 
		
        Map[\((s = StringReplace[#, " " -> ""]; 
					
              A = StringTake[s, 1]; 
				
              AppendTo[ans, Thread[\({A, #}&\)[dissect[StringDrop[s, 2]]]]])
              \)&, G]; 
		
        Flatten[ans, 1]\  /. \ "ε" -> ""]\)

BNF[{"S -> SS|AA|b|ε", 
        "A -> AS|AA|BB|a", "B->b"}]

Given a word w and a single production {l, r}, we generate the set of all possible derivations.

oneDerivation[w_String, {l_, r_}]:=Map[StringReplacePart[w, r, #]&,StringPosition[w, l]]

oneDerivation["SSSxSxxS", {"S", "ab"}]

We generalize the above to a grammar acting on a set of words.

\(oneDerivation[words : {_String..}, G_] := 		
      Flatten[Outer[List, words, G] /. 
          \ {{a_, b_}, {a_, c_}} -> oneDerivation[a, {b, c}]]\)

oneDerivation[{"SxSxS", "xSx", "SASx"}, 
      BNF[{"S->Ay|ε", "A->b"}]]

We further generalize to obtain all the words that can be generated by exactly n derivations and of size at most m.

\(words[G_, n_, m_] := Select[derivations[G, n, m], LowerCaseQ]
\)\(derivations[G_, n_, m_] := deriv[{"S"}, G, n, m]
	\)deriv[{}, _, _, _] := {}\(deriv[w_, _, 0, _] := w
\)\(deriv[w_, G_, n_, m_] := 
      Module[{d = oneDerivation[w, G], f}, 
		
        f = Select[Union[d], StringLength[#] ≤ m&]; 
		
        deriv[f, G, n - 1, m]]\)

Table[
      derivations[BNF[{"S->aSa|bSb|a|b|ε"}], n, 5], {
        n, 3}]

Table[
      words[BNF[{"S->aSa|bSb|a|b|ε"}], n, 5], {n, 4}]

The Cocke-Kasami-Younger algorithm requires grammars in Chomsky normal form, that is, ε ∉ L(G) and each of its productions are of the form A -> BC or  A -> a. Any CFG G such that ε ∉ L(G) possesses a Chomsky normal form.

We will neeed the auxiliary function yux below to yuxtapose sets of variables:

yux[B_, C_] := Flatten[Outer[StringJoin, B, C]]

yux[{"A", "B"}, {"C", "D", "E"}]

Recognition through building the table t, t\(TraditionalForm\`\_\(i, j\)\) contains the set of variables A such that A \(TraditionalForm\`\(\(⟹\ \)\&*\)\)x\(TraditionalForm\`\(\ \_\(i, j\)\)\)

\(CKY[w_, G_] := 
      Module[{A, t, n, x = Characters[w], f, i, j}, 
		
        t = Map[{Cases[G, {A_, #} -> A]}&, x]; 
		n = Length[x]; 

        		Do[
			
          AppendTo[t[[i]], 
            Union[Flatten[
                Map[
				
                  \((f = yux[t[[i, #]], 
                          t[[i + #, 
                            j + 1 - #]]]; 
					
                      First\ /@\ Select[G, MemberQ[f, Last[#]]&]
				)
                      \)&, Range[j]]]]]
			, {j, n}, {i, n - j}]; 
		t]
        \)

\(G\_1 = BNF[{"S -> SS|AA|b", "A -> AS|AA|a"}]; 

    w\_1 = "aabb"; 
MatrixForm[CKY[w\_1, G\_1]]\)

\(G\_2 = 
      BNF[{"S -> AB|BC", "A -> BA|a", "B -> CC|b", 
          "C -> AB|a"}]; 
w\_2 = "baaba"; 

    MatrixForm[CKY[w\_2, G\_2]]\)

The following computes the left parsing we seek through the use of an auxiliary recursive function.

\(parseCKY[w_, G_] := 
      Module[{V = CKY[w, G], parse}, 
				

        parse[i_, i_, A_] := First[Position[G, {A, StringTake[w, {i, i}]}]]; 
        
parse[i_, j_, A_] := 
          Module[{k, B, C, p, m}, 
		k = i + 1; 
		
            While[
			
              B = V[[i, k - i]]; 
			
              C = V[[k, j - k + 1]]; 

              			p = 
                Select[G, 
                  \((\((First[#] == A)\)\  && \ MemberQ[yux[B, C], Last[#]])
                      \)&, 1]; 
			p == {}, \(k++\)]; 
		p = First[p]; 
            
		m = 
              \(Position[G, p]\)[[1, 1
                ]]; 
		
		
            Join[{m}, parse[i, k - 1, StringTake[Last[p], 1]], 
              parse[k, j, StringTake[Last[p], \(-1\)]]]]; 
	
			
        If[Not[MemberQ[Last[V[[1]]], 
              "S"]], {}, parse[1, StringLength[w], "S"]]]\)

parseCKY[(Subscript[w, 1]), (Subscript[G, 1])]

As (Subscript[G, 1])= {{"S","SS"},{"S","AA"},{"S","b"},{"A","AS"},{"A","AA"},{"A","a"}}, the above implies the following sequence of left derivations:

			S, AA, aA, aAS, aaS, aaSS, aabS, aabb

parseCKY[(Subscript[w, 2]), (Subscript[G, 2])]

\(G\_3 = 
      BNF[{"S -> AC|BD|a|b|AA|BB", "A -> a", 
          "B -> b", "C -> SA", "D -> SB"}]; 

    w\_3 = "aaaaaaaaaa"; 
Table[parseCKY[w\_3, G\_3]]\)

The following generates all palindromes of size n

pal[1] := {"a", "b"}pal[2] := {"aa", "bb"}\(pal[n_] := 
      Module[{p = pal[n - 2]}, 
		
        Join[Map[\(("a"<>#<>"a")\)&, p], 
          Map[\(("b"<>#<>"b")\)&, p]]]\)

We can examine all their parsings:

Map[{#, Timing[parseCKY[#, (Subscript[G, 3])]]}&, pal[6]]

Productions 3 and 4 are missing, hence we can afford to delete them from (Subscript[G, 3]); their only purpose is to be able to parse pal[1].
All of the above parsings start as 1, 7, 9 if  the corresponding palindrome begins with an "a" or 2, 8, 10 if  it begins with a "b".Also, all have the same length.

Similarly, we can explore the grammar generating the set of all words in {a, b} having an even number of a´s generated by the following grammar:

(Subscript[G, 4]) = 
      BNF[{"S -> AS|CS|AA|CA|DE|DD|b", "C -> b", 
          "B -> CB|b", "A -> DE|DD", "E -> BD", 
          "D -> a"}];

That set can be generated by function evenA below:

oddA[1] := {"a"}oddA[2] := {"ab", "ba"}\(oddA[n_] := 
      Join[Map[\(("a"<>#)\)&, evenA[n - 1]], 
        Map[\(("b"<>#)\)&, oddA[n - 1]]]
\)evenA[1] := {"b"}evenA[2] := {"aa", "bb"}evenA[n_] := 
      Join[Map[("a"<>#)&, oddA[n - 1]], 
        Map[("b"<>#)&, evenA[n - 1]]]

evenA[4]

Map[{#, Timing[parseCKY[#, (Subscript[G, 4])]]}&, evenA[6]]

Note the characteristic parsing for abbbba

In this part we follow the section "A Good Practical Algorithm" in Harrison´s book, where a version of Earley algorithm \ispresented. This algorithm is the most practical, genarl context-free recognition and parsing algorithm. In general it is O((n^3)), but takes O((n^2)) on any unambiguous CFG and it is reported to be actually linear on a wide variety of useful grammars. We will utilize the following CFG to test this algorithm.

\(G\_1 = BNF[{"S -> aSa|bSb|a|b|ε"}]; 

    G\_2 = BNF[{"S -> AB", "A -> ε", 
          "B -> CDC", "C -> ε", 
          "D -> a"}]; 
G\_3 = BNF[{"S -> S*S|S+S|a"}]; 

    G\_4 = BNF[{"S -> ABC | CD", "A -> C", 
          "B -> DA | A", "C -> AB | ε", 
          "D -> a"}]; 

    G\_5 = BNF[{"S -> aSb | ε"}]; 

    G\_6 = BNF[{"S -> aB | bA", "A -> a | aS | bAA", 
          "B -> b | bS | aBB"}]; \)

A) DETECTION OF NULLABLE VARIABLES

			nullV[G]={A | \(TraditionalForm
      \`\(\(A\ ⟹ε\ \)\&*\)\)}

\(nullV[G_] := 
      Module[{A, u, c, g, s, t}, 
		
        t = FixedPoint[
            \((u = #; \ 
					c = Cases[u, {A_, ""} -> A]; 

                					s = Thread[\ \(\((# -> "")\)&\)[c]]; 

                					g = Select[u, Not[MemberQ[c, First[#]]]&]; 
                Map[{First[#], StringReplace[Last[#], s]}&, g])\)&, G]; 
		
        Complement[First\ /@\ G, First\ /@\ t]]\)

nullV[(Subscript[G, 1])]nullV[(Subscript[G, 2])]nullV[(Subscript[G, 3])]nullV[(Subscript[G, 4])]nullV[(Subscript[G, 5])]nullV[(Subscript[G, 6])]

B) OPERATIONS ON A  SET Q OF DOTTED RULES AND A SET R OF VARIABLES

Definition. If A -> αβ is a production, we say that A -> α ▪ β is a dotted rule.
Definition. Let Q be a set of dotted rules and R a set of variables:

			Q ⊗ R = { A -> αBβ▪γ | A -> α▪Bβγ is in Q, B∈R and β\(TraditionalForm\`\(\ 
      \(\(⟹\&*\)ε\)\)\)}

\(\((Q_\ ⊗\ R_)\)\_G_ := 
      Module[{nV = nullV[G], q, r, i, j, ans = {}}, 
		
        q = Cases[
            Q, {A_, {α___, ".", B_\  /; \ MemberQ[R, B], 
                  βγ___}}\  -> 
              \ {A, {α, B, {βγ}}}]; 
		
        Map[\((
				j = #; \ 
              PrependTo[
                j[[\(-1\), \(-1\)]], 
                "."]; 
				AppendTo[ans, j]; 
				
              r = #[[\(-1\), \(-1\)]]; 

              				i = 1; 
				
              While[\((i ≤ Length[r])\)\  && \ 
                  MemberQ[nV, r[[i]]], 

                					j = #; 
					
                j[[\(-1\), \(-1\)]] = 
                  Insert[j[[\(-1\), 
                      \(-1\)]], ".", i + 1]; 

                					AppendTo[ans, j]; \ \(i++\)]
		)\)&, q]; 
		
        \({First[#], Flatten[Last[#]]}&\)\ /@\ ans]\)

dl = BNF[{"S->A.BCaB", "A->D.CBS"}](Subscript[((Map[{First[#],  Characters[Last[#]]}&, dl]⊗{"B", 
            "C", "D", "B"})), (Subscript[G, 4])])

(Subscript[(({{"S", {"A", ".", "B"}}}⊗{"B"})
        ), (Subscript[G, 2])])

C) COMPUTATION OF LEADERS

 Definition. leaders[R,G]={ B |  \(TraditionalForm\`\(\(B\ ⟹C\ \)\&*\)\) for some CϵR}

leaders[R,G]=R ⋃ leaders[{H | H -> CBD for some BϵR and C,D ϵ (nullV[G])*, not both empty}, G]

\(subsetQ[A_, a_] := \((Union[A, a] == Union[A])\)
	\)\(leaders[R_, G_] := 
      Module[{h, nV = nullV[G], CBDForm}, 
		
		
        CBDForm[{C___, B_\ , D___}] := 
          True\  /; \ MemberQ[R, B]\  && \ \ subsetQ[nV, {C, D}]; 
					
        
		h = Cases[G, {H_\ , k_\  /; CBDForm[Characters[k]]} -> H]; 
        \ 
		If[subsetQ[R, h], R, leaders[Union[R, h], G]]]\)

leaders[{"D"}, (Subscript[G, 4])]

Definition. Let Q be a set of dotted rules and R a set of variables:

	Q ⊙ R	 = { A -> αBβ▪γ | A -> α▪Bβγ is in Q, B \(TraditionalForm\`\(\ \(⟹\&*\)\)\) C for some CϵR and β\(TraditionalForm\`\(\ 
      \(\(⟹\&*\)ε\)\)\)}
		=Q ⊗ leaders[R,G]

(Subscript[((Q_ ⊙ R_)), G])_ := 
      (Subscript[((Q ⊗ leaders[R, G])), G])  /; 
        Length[Dimensions[R]] == 1

dl = BNF[{"S->A.BCaB", "A->D.CBS"}](Subscript[((Map[{First[#],  Characters[Last[#]]}&, dl]⊙{"D"})
        ), (Subscript[G, 4])])

(Subscript[(({{"S", {"A", ".", "B"}}}⊙{"D"})
        ), (Subscript[G, 2])])

D) EXTENSION TO BOTH Q AND R SETS OF DOTTED RULES

Definition. Q ⊗ R = { A  ->  
                  αBβ▪γ  |  A 
                     ->  
                    α▪Bβγ is in 
                      Q, B->η▪∈R and β\(\ 
                        \(\(⟹\&*\)ε\)\)}
=Q ⊗ {
                B  |  B -> η▪ ∈ R}
                
		Q ⊙ R = { A  ->  
                αBβ▪γ  |  A  
                  ->  
                  α▪Bβγ is in Q
                    , B \(\ \(⟹\&*\)\) C for some C such that C ->η▪ϵR and β\(\ 
                    \(\(⟹\&*\)ε\)\)}
=Q ⊙  {
              C  |  C -> η▪ ∈ R}

\(\((Q_\ ⊗\ R_)\)\_G_ := 
      \((Q\ ⊗\ Cases[R, {A_, {___, "."}}\  -> \ A])
            \)\_\(G\ \) /; Length[Dimensions[R]] > 1
\)(Subscript[((Q_ ⊙ R_)), G])_ := 
      (Subscript[((Q ⊙ Cases[R, {A_, {___, "."}} ->  A])), G 
          ]) /; Length[Dimensions[R]] > 1

\(u = {{"S", {".", "A", "B"}}, {"A", {"."}}, {
          "B", {".", "C", "D", "C"}}, {
          "C", {"."}}, {"D", {".", "a"}}, {
          "S", {"A", ".", "B"}}, {
          "B", {"C", ".", "D", "C"}}}; 

    v = {{"D", {"a", "."}}}; 

    \((u\ ⊙\ v)\)\_\(G\_2\)\)

E) CONSTRUCTION OF THE PREDICTOR

COMPUTATION OF FOLLOWERS

Definition.  followers[R,G]={ C |  \(TraditionalForm\`\(\(B\ ⟹Cη\ \)\&*\)\) for some BϵR and some η ∈V*}

followers[R,G]=R ⋃ followers[{H | B -> CHD for some BϵR and C,D ϵ (nullV[G])*, not both empty}, G]

followers[{}, _] := {}\(followers[R_, G_] := 
      Module[{g, h = {}, nV = nullV[G], carryOn}, 
					
		
        g = Cases[
            G, {B_\ \  /; \ MemberQ[R, B], C_} -> {B, Characters[C]}]; 

        		Map[\((
			i = 1; 
				carryOn = True; 
				
              While[carryOn\  && \ \((i ≤ Length[Last[#]])\)\  && 
                  UpperCaseQ[
                    \(Last[#]\)[[i]]], \ 
                AppendTo[h, 
                  \(Last[#]\)[[i]]]; 

                					
                If[Not[MemberQ[nV, 
                      \(Last[#]\)[[i
                        ]]]], carryOn = False]; \ \(i++\)]
                
			)\)&, g]; \ 
		
        Union[R, followers[Complement[h, R], G]]]\)

followers[{"S"}, (Subscript[G, 1])]followers[{"S"}, (Subscript[G, 2])]followers[{"S"}, (Subscript[G, 3])]followers[{"S"}, (Subscript[G, 4])]followers[{"S"}, (Subscript[G, 5])]followers[{"S"}, (Subscript[G, 6])]

Definition.  

	predict(R) = { C -> γ ▪ ξ | C -> γ ξ is a production, γ \(TraditionalForm\`\( ⇒ \&*\)\) ε, B \(TraditionalForm\`\( ⇒ \&*\)\) C η for some B ϵ R and some η ϵ V* }

\(predict[R_, G_] := 
      Module[{nV = nullV[G], f = followers[R, G], g, ans, i}, \ 
		
		
        g = Cases[
            G, {C_\ \  /; \ MemberQ[f, C], α_} 
              -> {C, Characters[α]}]; 
		
        ans = Map[{First[#], Join[{"."}, Last[#]]}&, g]; \ 
		
        Map[\((
			i = 1; 
				
              While[\((i ≤ Length[Last[#]])\)\  && \ 
                  MemberQ[nV, 
                    \(Last[#]\)[[i]]], 
                AppendTo[ans, {First[#], Insert[Last[#], ".", i + 1]}]; 
                \(i++\)]; 
			)\)&, g]; 
		ans]\)

predict[{"S"}, (Subscript[G, 1])]predict[{"S"}, (Subscript[G, 2])]predict[{"S"}, (Subscript[G, 3])]predict[{"S"}, (Subscript[G, 4])]predict[{"S"}, (Subscript[G, 5])]predict[{"S"}, (Subscript[G, 6])]

EXTENSION TO A SET OF DOTTED RULES

Definition.
		 predict(R) =predict({ B | A -> α ▪ Bβ is a production})

predict[R_, G_] := 
      predict[Cases[R, {_, {___, ".", B_, β___}} -> B], G]  
         /; Length[Dimensions[R]] > 1

predict[{{"B", {"C", "D", ".", "C"}}, {
          "B", {"C", "D", "C", "."}}, {
          "D", {"a", "."}}, {
          "S", {"A", "B", "."}}}, (Subscript[G, 2])]

F) MAIN ALGORITHM

Construction of the parse matrix earley

\(earley[w_, G_] := 
      Module[{n, i, j, k, t}, 
		n = StringLength[w]; 
		
		
        t = Table[{}, {i, n + 1}, {j, n + 1}]; 
		
		
        t[[1, 1]] = 
          predict[{"S"}, G]; 
		
        Do[
			
          Do[
				
            t[[i, j]] = 
              \((t[[i, j - 1]]\ 
                    ⊗\ {StringTake[w, {j - 1}]})\)\_G, {i, 
              j - 1}]; 
			
          Do[
				
            t[[k, j]] = 
              Union[t[[k, j]], 
                \((t[[k, k
                        ]]⊙\ 
                      t[[k, j]])\)\_G]; 
            
				
            Do[
					
              t[[i, j]] = 
                Union[t[[i, j]], 
                  \((t[[i, k]]\ 
                        ⊗\ 
                        t[[k, j]])
                      \)\_G], {i, k - 1, 1, \(-1\)}], {k, j - 1, 1, \(-1\)}]; 
          
			t[[j, j]] = 
            predict[Union\ \ @@\ 
                Table[t[[i, j]], {i, 
                    j - 1}], G], {j, 2, n + 1}]; 
		t]\)

To aid in the formatting of the output we make use of function showDottedPairs below:

showDottedPairs[{}] := {""}showDottedPairs[{A_, B_}] := A<>"->"<>StringJoin[B]

\(e\_2 = earley["a", G\_2]; 

    Table[If[e\_2[[i, j]] 
            ≠ {}, 
          Map[showDottedPairs, 
              e\_2[[i, j]]]\  // \ 
            MatrixForm, {""}], {i, 2}, {j, 2}]\ \  // \ MatrixForm\)

\(e\_3 = earley["a+a*a", G\_3]; 

    Table[If[e\_3[[i, j]] 
            ≠ {}, 
          Map[showDottedPairs, 
              e\_3[[i, j]]]\  // \ 
            MatrixForm, {""}], {i, 6}, {j, 6}]\ \  // \ MatrixForm\)

G) PARSING

With the help of matrix early we generate a right parsing of a given word.

\(\(parse[w_, G_] := 
      Module[{t = earley[w, G], c, par, ans = {}}, 
		
		
        par[i_, j_, {A_, Apm_}] := 
          Module[{m, j0, n, k, u}, 
					
				j0 = j; 
				
            m = Position[G, {A, StringJoin[Apm]}]; 
				
            AppendTo[ans, m[[1, 1]]]; \ 
            
					
            Do[
						
              If\ [Not[
                  UpperCaseQ[Apm[[n]]]], 
                j0 = j0 - 1, 
						k = j0; 
					
                While[
							
                  Not[\((i ≤ k)\)\  && \ 
                      \((u = Cases[
                            t[[k, j0
                              ]], {
                                Apm[[n
                                  ]], {α___, 
                                  "."}} 
                              -> {
                                Apm[[n
                                  ]], {α}}]; \ 
                        u ≠ {})\)\  && \ 
                      MemberQ[
                        t[[i, k]], {A, 
                          Insert[Apm, ".", n]}]], k = k - 1]; 

                							par[k, j0, First[u]]; 
						j0 = k], {
                n, Length[Apm], 1, \(-1\)}]]; 
		
		
		
        c = Cases[
            Last[First[t]], {"S", {α___, "."}} 
              -> {"S", {α}}]; 
		
        If[c ≠ {}, 
			
          par[1, StringLength[w] + 1, 
            c[[1]]], 
          Return["Error"]]; 
						ans]		
\)\)

(Subscript[G, 3])parse["a+a*a", (Subscript[G, 3])]

The former parsing corresponds to the right parse: S, S*S, S*a, S+S*a, S+a*a, a+a*a

(Subscript[G, 6])parse["abaaabbabb", (Subscript[G, 6])]

The former parsing corresponds to the right parse:
		
		S, aB, abS, abaB, abaaBB, abaaaBBb, abaaaBbb, abaaabSbb, abaaabbAbb, abaaabbabb

parse["aaabbb", (Subscript[G, 5])]