Context-Free Grammars

Preliminary and incomplete version
28 January 1994

Introduction

The command AcceptQ[grammar,string,integer] determines if the string is in the language generated by the grammar.  It will stop if its attempt to produce a derivation reaches a depth of integer.  The grammar is given as a list of lists, each list representing a production as an ordered pair of strings (see the Examples section).  AcceptQ performs a bottom up construction of all possible derivations (and prints the successive stages), and will always succeed if the grammar has the property that the right side of each production is longer than the left side.

Implementation

FindPlaces[grammar_List,s_String] :=
   StringPosition[s,Part[#,2]]& /@ grammar
(*FindPlaces[grammar,string] produces a list of pairs {m,n}
   where the right side of a production in grammar occurs
   as a substring of string from position m to position n.
   The lists of pairs are grouped by production: the kth
   list of pairs correspond to the occurrences of the right
   side of production k of grammar.*)

BDL[placeslist_List,r_String,s_String] :=
   If[Length[placeslist]>0,
      StringInsert[StringDrop[s,#],r,Part[#,1]]&
           /@ placeslist,
      {}
     ]
(*placeslist should consist of a list of pairs (m,n) of positive
  integers.  BDL[placeslist,r,s] produces a list of strings,
  each of which is the result of replacing characters m through
  n of s with the string r for one of the pairs (m,n) of
  placeslist.*)

BackDerive[grammar_List,s_String] :=
   Module[{places = StringPosition[s,Part[#,2]]& /@ grammar},
  (BDL[FindPlaces[grammar,s][[#]],grammar[[#]][[1]],s]& /@
   Table[k,{k,Length[grammar]}])]

BackDerive[grammar_List,x_List] :=
   BackDerive[grammar,#]& /@ x

SimpleBackDerive[grammar_List,x_List] :=
   Union[Flatten[BackDerive[grammar,x]]]

EmptyQ[x_List] := Length[x]==0

AcceptQ[grammar_List,s_String,maxit_Integer:30] :=
  Module[{tries=List[s],k=0},
   (While[(!MemberQ[tries,"S"] && !EmptyQ[tries] && k++<maxit),
        (tries=SimpleBackDerive[grammar,tries];
           Print[k," ",tries])
          ];
     MemberQ[tries,"S"])
        ]

Examples

Execute the following definitions, giving you a grammar g1 and some strings.  Then execute the commands.

g1 := {{"S","SS"},
  {"S","aSb"},
  {"S","bSa"},
  {"S","cC"},
  {"C","cC"},
  {"C","c"}}

st = "abSabbaSbSacCab"

st2="aSbbcCa"

FindPlaces[g1,"aSSS"] (*Example*)

BDL[{{1,2},{2,5}},"xy","abcde"]

SimpleBackDerive[g1,{"ab","acCb","aSbb","SS"}]

AcceptQ[g1,st]

AcceptQ[g1,st2]

Acknowledgments

This work was supported by the Consolidated Natural Gas Corporation

Author & Copyright

Charles Wells
Department of Mathematics
Case Western Reserve University
University Circle
Cleveland, OH 44106-7058

Phone 216 368 2893 or 216 774 1926

Email cfw2@po.cwru.edu

Copyright 1994 by Charles Frederick Wells.  May be freely redistributed for noncommercial purposes provided it is unchanged.