home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / Other Langs / abc / examples / grammar / article next >
Encoding:
Text File  |  1994-04-01  |  9.9 KB  |  385 lines  |  [TEXT/R*ch]
  1. GRAMMAR TOOLS IN ABC
  2.  
  3. When I have to work with grammars, I always use ABC to do it. Among
  4. the advantages are that you can do the work interactively, that you
  5. can very quickly build additional tools, and that you have the already
  6. powerful programming environment at your disposal.
  7.  
  8. What follows is a brief description of some of the tools I use, with
  9. an example. There is no description of ABC: you can find a quick
  10. description of the language by ftp-ing the file "abc.intro" from
  11. uunet.uu.net, mcsun.eu.net, or hp4nl.nluug.nl, in directory
  12. {pub}/{programming}/languages/abc, or by sending the message
  13.  
  14.     request: programming/languages/abc
  15.     topic: abc.intro
  16.  
  17. to info-server@hp4nl.nluug.nl. The file tells you where to get more
  18. information about ABC (there's a book), and how to get the
  19. implementations (they're free).
  20.  
  21. Some of what follows is also presented in the book, though at a more
  22. relaxed pace :-).
  23.  
  24. (For didactic reasons, what is presented here differs in detail from
  25. the distributed code.)
  26.  
  27. GRAMMARS
  28.  
  29. The representation that I use is more or less a direct transcription
  30. of what a grammar is. I use a table whose keys are texts (i.e.
  31. strings) representing the nonterminals of the language, and whose
  32. items are sets of alternatives. Each alternative is a sequence of
  33. texts, representing terminals and nonterminals. So here is a how-to
  34. that displays a grammar in this form:
  35.  
  36.     HOW TO DISPLAY grammar:
  37.        FOR name IN keys grammar:
  38.           WRITE "`name`: " /
  39.           FOR alt IN grammar[name]:
  40.          WRITE "    "
  41.          FOR symbol IN alt:
  42.             WRITE symbol, " "
  43.          WRITE /
  44.  
  45. and as example:
  46.  
  47.     >>> DISPLAY sentence
  48.     ADJ:
  49.         EMPTY
  50.         clever
  51.         shy
  52.     BOY:
  53.         John
  54.         Kevin
  55.     EMPTY:
  56.  
  57.     GIRL:
  58.         Mary
  59.         Susan
  60.     OBJ:
  61.         SUBJ
  62.     SENT:
  63.         SUBJ loves OBJ
  64.     SUBJ:
  65.         ADJ BOY
  66.         ADJ GIRL
  67.  
  68. You can generate a random phrase from a grammar with the following:
  69.  
  70.     HOW TO GENERATE sym FROM grammar:
  71.        SELECT:
  72.           sym in keys grammar: \ Nonterminal
  73.          FOR new IN choice grammar[sym]:
  74.             GENERATE new FROM grammar
  75.           ELSE: \ Terminal symbol
  76.          WRITE sym, " "
  77.  
  78.     >>> GENERATE "SENT" FROM sentence
  79.     Susan loves clever John
  80.  
  81. SETS
  82.  
  83. Here are some necessary functions on sets. Set union:
  84.  
  85.     HOW TO RETURN set1 with set2: \ Union
  86.        FOR x IN set2:
  87.           IF x not.in set1:
  88.          INSERT x IN set1
  89.        RETURN set1
  90.  
  91. Set difference:
  92.  
  93.     HOW TO RETURN set1 less set2: \ Difference
  94.        FOR x IN set2:
  95.           IF x in set1:
  96.          REMOVE x FROM set1
  97.        RETURN set1
  98.  
  99. Here is a function that collects all symbols used in the rules of a grammar:
  100.  
  101.     HOW TO RETURN used grammar: \Collect all used symbols
  102.        PUT {} IN all
  103.        FOR rule IN grammar:
  104.           FOR alt IN rule:
  105.          FOR sym IN alt:
  106.             IF sym not.in all:
  107.                INSERT sym IN all
  108.        RETURN all
  109.  
  110.     >>> WRITE used sentence
  111.     {"ADJ"; "BOY"; "EMPTY"; "GIRL"; "John"; "Kevin"; "Mary";
  112.      "OBJ"; "SUBJ"; "Susan"; "clever"; "loves"; "shy"}
  113.  
  114. The terminals of the grammar are all the symbols less the nonterminals:
  115.  
  116.     >>> WRITE (used sentence) less keys sentence
  117.     {"John"; "Kevin"; "Mary"; "Susan"; "clever"; "loves"; "shy"}
  118.  
  119. and the unused nonterminals (such as the root symbol) are the
  120. nonterminals less the used symbols:
  121.  
  122.     >>> WRITE (keys sentence) less used sentence
  123.     {"SENT"}
  124.  
  125. For neater output, the function "listed" converts a set to a text:
  126.  
  127.     HOW TO RETURN listed set:
  128.        PUT "" IN line
  129.        FOR element IN set:
  130.           PUT line ^ "`element` " IN line
  131.        RETURN line
  132.  
  133.     >>> WRITE listed ((used sentence) less keys sentence)
  134.     John Kevin Mary Susan clever loves shy
  135.  
  136. A useful set is the set of nonterminals that can generate empty. This
  137. is generated by repeatedly doing a pass over the rules that we don't
  138. know yet can generate empty, until we find no more:
  139.  
  140.     HOW TO RETURN empties grammar:
  141.        PUT keys grammar, {} IN to.do, empties
  142.        WHILE SOME name IN to.do HAS empty.rule:
  143.           INSERT name IN empties
  144.           REMOVE name FROM to.do
  145.        RETURN empties
  146.     empty.rule:
  147.        REPORT SOME alt IN grammar[name] HAS empty.alt
  148.     empty.alt:
  149.        REPORT EACH sym IN alt HAS sym in empties
  150.  
  151.     >>> WRITE listed empties sentence
  152.     ADJ EMPTY
  153.  
  154. RELATIONS
  155.  
  156. Relations between symbols of the grammar are the essential element of
  157. the grammar tools. A relation is represented as a table whose keys are
  158. symbols, and whose items are sets of symbols.
  159.  
  160. For instance, if symbol b follows symbol a in some rule, "b" will be
  161. in the set for follows["a"], so you can say, for instance:
  162.  
  163.     IF "b" in follows["a"]: ....
  164.  
  165. Relations are sparse (i.e. a symbol is not in the keys of the relation
  166. if the set of elements is empty), so we use the following to access a
  167. relation:
  168.  
  169.     HOW TO RETURN relation for k: \relation[k] for sparse relations
  170.        IF k in keys relation:
  171.           RETURN relation[k]
  172.        RETURN {}
  173.  
  174. To add an element to a relation, we use this:
  175.  
  176.     HOW TO ADD element TO relation FOR thing:
  177.        IF thing not.in keys relation: \First time
  178.           PUT {} IN relation[thing]
  179.        IF element not.in relation[thing]:
  180.           INSERT element IN relation[thing]
  181.  
  182. though you may prefer
  183.  
  184.     HOW TO ADD element TO relation FOR thing:
  185.        PUT (relation for thing) with {element} IN relation[thing]
  186.  
  187. For instance:
  188.  
  189.     >>> ADD "b" TO follows FOR "a"
  190.  
  191. We'll display a relation with:
  192.  
  193.     HOW TO SHOW relation:
  194.        FOR k IN keys relation:
  195.           WRITE "`k`: ", listed relation[k] /
  196.  
  197. Here are some general functions on relations. The inverse:
  198.  
  199.     HOW TO RETURN inverse relation:
  200.        PUT {} IN inv
  201.        FOR k IN keys relation:
  202.           FOR x IN relation[k]:
  203.          ADD k TO inv FOR x
  204.        RETURN inv
  205.  
  206. The product of two relations (a P c iff a R1 b and b R2 c):
  207.  
  208.     HOW TO RETURN r1 prod r2: \product of relations
  209.        PUT {} IN prod
  210.        FOR c IN keys r2:
  211.           FOR b IN r2[c]:
  212.          IF b in keys r1:
  213.             FOR a IN r1[b]:
  214.                ADD a TO prod FOR c
  215.        RETURN prod
  216.  
  217. The closure:
  218.  
  219.     HOW TO RETURN closure r:
  220.        FOR i IN keys r:
  221.           FOR j IN keys r:
  222.          IF i in r[j]:
  223.             PUT r[i] with r[j] IN r[j]
  224.        RETURN r
  225.  
  226. To make a relation reflexive, we use the following. Since relations
  227. are sparse, we also have to pass the set of symbols that it must be
  228. reflexive over:
  229.  
  230.     HOW TO RETURN symbols reflexive relation: \make the relation reflexive
  231.        FOR sym IN symbols:
  232.           ADD sym TO relation FOR sym
  233.        RETURN relation
  234.  
  235. SOME EXAMPLES OF RELATIONS
  236.  
  237. To collect the *direct* followers for each symbol, we walk along each
  238. alternative, collecting adjacent symbols. There is one catch: in a
  239. rule like:
  240.  
  241.     SENT: the ADJ PERSON
  242.  
  243. "the" and "ADJ" are adjacent, but if "ADJ" can generate empty, then so
  244. are "the" and "PERSON":
  245.  
  246.     HOW TO RETURN followers grammar:
  247.        PUT {}, empties grammar IN foll, empty
  248.        FOR rule IN grammar:
  249.           FOR alt IN rule:
  250.          TREAT ALT
  251.        RETURN foll
  252.     TREAT ALT:
  253.        FOR i IN {1..#alt-1}:
  254.           PUT alt item i IN this
  255.           TREAT PART
  256.     TREAT PART:
  257.        FOR j IN {i+1..#alt}:
  258.           PUT alt item j IN next
  259.           ADD next TO foll FOR this
  260.           IF next not.in empty: QUIT
  261.  
  262.     >>> SHOW followers sentence
  263.     ADJ: BOY GIRL
  264.     SUBJ: loves
  265.     loves: OBJ
  266.  
  267. To collect the direct starter symbols of each rule, you also have to
  268. deal with symbols that produce empty:
  269.  
  270.     HOW TO RETURN heads grammar:
  271.        PUT {}, empties grammar IN heads, empty
  272.        FOR name IN keys grammar:
  273.           FOR alt IN grammar[name]:
  274.          TREAT ALT
  275.        RETURN heads
  276.     TREAT ALT:
  277.        FOR i IN {1..#alt}:
  278.           PUT alt item i IN head
  279.           ADD head TO heads FOR name
  280.           IF head not.in empty: QUIT
  281.  
  282.     >>> SHOW heads sentence
  283.     ADJ: EMPTY clever shy
  284.     BOY: John Kevin
  285.     GIRL: Mary Susan
  286.     OBJ: SUBJ
  287.     SENT: SUBJ
  288.     SUBJ: ADJ BOY GIRL
  289.  
  290. Similarly for the direct enders:
  291.  
  292.     HOW TO RETURN tails grammar:
  293.        PUT {}, empties grammar IN tails, empty
  294.        FOR name IN keys grammar:
  295.           FOR alt IN grammar[name]:
  296.          TREAT ALT
  297.        RETURN tails
  298.     TREAT ALT:
  299.        FOR i' IN {-#alt..-1}:
  300.           PUT -i' IN i
  301.           PUT alt item i IN tail
  302.           ADD tail TO tails FOR name
  303.           IF tail not.in empty: QUIT
  304.  
  305. The closure of the head relation represents all symbols that can start
  306. a rule, either directly or indirectly:
  307.  
  308.     >>> SHOW closure heads sentence
  309.     ADJ: EMPTY clever shy
  310.     BOY: John Kevin
  311.     GIRL: Mary Susan
  312.     OBJ: ADJ BOY EMPTY GIRL John Kevin Mary SUBJ Susan clever shy
  313.     SENT: ADJ BOY EMPTY GIRL John Kevin Mary SUBJ Susan clever shy
  314.     SUBJ: ADJ BOY EMPTY GIRL John Kevin Mary Susan clever shy
  315.  
  316. Symbol b may follow symbol a in a phrase if b follows a in an
  317. alternative, or if B follows A in an alternative and b is in heads*(B)
  318. and a is in tails*(A). This is expressed as the product
  319.     head* . follow . inverse(tail*).
  320.  
  321. Now we have enough to define a command that prints for each symbol in
  322. an alternative what may follow that symbol at that point:
  323.  
  324.     HOW TO SHOW LOCAL FOLLOWERS grammar:
  325.        PUT (used grammar) with keys grammar IN symbols
  326.        PUT symbols reflexive (closure heads grammar) IN head.star
  327.        PUT symbols reflexive (closure tails grammar) IN tail.star
  328.        PUT followers grammar IN follow
  329.        PUT (head.star prod follow) prod (inverse tail.star) IN deep.follow
  330.        FOR parent IN keys grammar:
  331.           FOR alt IN grammar[parent]:
  332.          TREAT ALT
  333.     TREAT ALT:
  334.        ANNOUNCE ALT
  335.        FOR i IN {1..#alt}:
  336.           TREAT SYM
  337.     TREAT SYM:
  338.        PUT alt item i IN sym
  339.        WRITE "    `sym`: ", listed local.follow /
  340.     local.follow:
  341.        PUT {} IN foll
  342.        FOR j IN {i+1..#alt}:
  343.           PUT alt item j IN next
  344.           PUT foll with (head.star for next) IN foll
  345.           IF next not.in empty:
  346.          RETURN foll
  347.        RETURN foll with (deep.follow for parent)
  348.     ANNOUNCE ALT:
  349.        WRITE "`parent`: ", listed alt /
  350.  
  351. This prints each alternative separately, followed by each symbol of
  352. the alternative indented one to a line followed by the symbols that
  353. can follow it at that point.
  354.  
  355. For example:
  356.  
  357.     >>> SHOW LOCAL FOLLOWERS sentence
  358.     ADJ: EMPTY
  359.         EMPTY: BOY GIRL John Kevin Mary Susan
  360.     ADJ: clever
  361.         clever: BOY GIRL John Kevin Mary Susan
  362.     ADJ: shy
  363.         shy: BOY GIRL John Kevin Mary Susan
  364.     BOY: John
  365.         John: loves
  366.     BOY: Kevin
  367.         Kevin: loves
  368.     EMPTY:
  369.     GIRL: Mary
  370.         Mary: loves
  371.     GIRL: Susan
  372.         Susan: loves
  373.     OBJ: SUBJ
  374.         SUBJ:
  375.     SENT: SUBJ loves OBJ
  376.         SUBJ: loves
  377.         loves: ADJ BOY EMPTY GIRL John Kevin Mary OBJ SUBJ Susan clever shy
  378.         OBJ:
  379.     SUBJ: ADJ BOY
  380.         ADJ: BOY John Kevin
  381.         BOY: loves
  382.     SUBJ: ADJ GIRL
  383.         ADJ: GIRL Mary Susan
  384.         GIRL: loves
  385.