home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compiler / 2232 < prev    next >
Encoding:
Text File  |  1993-01-23  |  6.3 KB  |  226 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!yale!mintaka.lcs.mit.edu!spdcc!iecc!compilers-sender
  3. From: jan@klikspaan.si.hhs.nl
  4. Subject: Recursive descent parsing is better than LL(1)
  5. Reply-To: jan@klikspaan.si.hhs.nl
  6. Organization: Compilers Central
  7. Date: Fri, 22 Jan 1993 16:41:50 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <93-01-160@comp.compilers>
  10. Keywords: parse, LL(1), theory
  11. References: <93-01-122@comp.compilers> <93-01-123@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 211
  14.  
  15. Barton Christopher Massey < bart@cs.uoregon.edu > writes:
  16.  
  17. > I will personally choose to use YACC or something similar for parsing until
  18. > I can implement an LL(1) parser generator which will take a reasonably
  19. > ad-hoc grammar and either transform it to an LL(1) grammar or report
  20. > failure to do so, "most of the time".
  21.  
  22. > In order to construct such a tool, I would like to prove or disprove the
  23. > following conjectures:
  24.  
  25. >     LL(1) Transformability:  There exists an algorithm
  26. >     which, given any grammar G which is unambiguous and
  27. >     describes an LL(1) language L(G), produces an LL(1)
  28. >     grammar G' for the language L(G).
  29.  
  30. >     LL(1) Decidability:  There exists an algorithm which,
  31. >     given any grammar G which is unambiguous and describes
  32. >     a language L(G), decides whether L(G) is an LL(1)
  33. >     language.
  34.  
  35. > After some thought, it still seems most likely to me that LL1T is true,
  36. > but I'm skeptical about LL1D .  I posted these conjectures to
  37. > comp.compilers previously, but didn't get too far with them then.  In a
  38. > way, I'm surprised if such apparently important questions haven't been
  39. > carefully studied, but I haven't found any very useful references yet.
  40.  
  41. Bill Purvis <W.Purvis@daresbury.ac.uk> writes:
  42.  
  43. > In Computer Journal, Vol 11, number 1, May 1968, J. Foster describes SID,
  44. > a syntax improving program which accepts a fairly arbitrary BNF
  45. > description and applies the neccesary transformations to produce an LL(1)
  46. > grammar (assuming that the language is LL(1). I think that that fully
  47. > covers the first conjecture.
  48.  
  49. > The program is pretty comprehensive and while it might not cover all
  50. > cases, I suspect that in practical terms it probably covers the second
  51. > conjecture.
  52.  
  53. This discussion is a bit blurred by the use of the clauses `given any
  54. grammar G' and `reasonably ad-hoc grammar'. I agree with Bill Purvis that
  55. SID does a good job on some fuzzy set of `reasonably good ad-hoc
  56. grammars'.
  57.  
  58. The general case `given any unambigous grammar G' cannot be solved by SID
  59. if it only uses the transformations substitution, elimination of left
  60. recursion and factorization.
  61.  
  62. I present a simple contra-example:
  63.  
  64. Consider the language defined by the next CFG:
  65.  
  66. S -> A
  67. S -> B
  68. A -> `x' A `y'
  69. A -> `a'
  70. B -> `x' B `z'
  71. B -> `b'
  72.  
  73. SID uses elimination of left recursion, factorisation and substitution to
  74. search for a better grammar.
  75.  
  76. The problem here is that A and B have `x' in common in their FIRST-sets.
  77. So let's substitute A and B in the S-rules giving:
  78.  
  79. S -> `x' A `y'
  80. S -> `a'
  81. S -> `x' B `z'
  82. S -> `b'
  83. A -> `x' A `y'
  84. A -> `a'
  85. B -> `x' B `z'
  86. B -> `b'
  87.  
  88. Two S-rules now start both with `x' so we have to factorize them giving:
  89.  
  90. S -> `x' S1
  91. S -> `a'
  92. S -> `b'
  93. A -> `x' A `y'
  94. A -> `a'
  95. B -> `x' B `z'
  96. B -> `b'
  97. S1 -> A `y'
  98. S1 -> B `z'
  99.  
  100. Now after solving the problem with the S-rules, we get the same problem
  101. with the S1-rules.
  102.  
  103. We can repeat both substitution and factiorisation on S1 giving:
  104.  
  105. S -> `x' S1
  106. S -> `a'
  107. S -> `b'
  108. A -> `x' A `y'
  109. A -> `a'
  110. B -> `x' B `z'
  111. B -> `b'
  112. S1 -> `x' S2
  113. S1 -> `a'
  114. S1 -> `b'
  115. S2 -> A `y' `y'
  116. S2 -> B `z' `z'
  117.  
  118. Giving rise to the same kind of conflict, but now on S2-rules.  Obviously
  119. the proces of substitution and factorization can be repeated
  120. indefinitedly.
  121.  
  122. The loop suggests the conjecture of decidability doesn't hold.
  123.  
  124. Foster expresses this problem with `SID may also report failure because
  125. its attempt to transform the grammar causes it to loop.'
  126.  
  127. But let's return to the initial discussion: recursive descent versus YACC.
  128.  
  129. Maybe we underestimate the power of recursive descent technique if only we
  130. could get rid of the idea each nonterminal should be mapped to one
  131. function recognizing the right sides of its productions.
  132.  
  133. Let's try a different approach: Each function recognizes right sides of
  134. one or more nonterminals, returning as a result the kind(s) of
  135. nonterminals recognized.
  136.  
  137. Let's return to the example grammar above:
  138.  
  139. S -> A
  140. S -> B
  141. A -> `x' A `y'
  142. A -> `a'
  143. B -> `x' B `z'
  144. B -> `b'
  145.  
  146. As we cannot discern A from B let's integrate them into one function AorB.
  147. This should answer the question `What did you see' with : neither (call
  148. this an error), A, B, or Both.
  149.  
  150. AorB might be modelled with a statediagram like:
  151.  
  152.                                        +-----------+    
  153.                            +------A-->-+    `y'    +---y---> result is A
  154.                            |           +-----------+
  155.      +--------+        +---+--+        =-----------+
  156. >----+   `x'  +---x-->-+ AorB +---B----+    `z'    +---z---> result is B
  157.      +--------+        +-+-+--+        +-----------+    
  158.                          | |           +-----------+---x---> result is A
  159.                          V +----Both---+ `y' or z' +    
  160.                       neither          +-----------+---y---> result is B
  161.                          |
  162.    conflicting inputs ---+---------------------------------> result is neither
  163.  
  164. As AorB has no Both exit, this branch could be pruned from the diagram.
  165.  
  166. In C this would look like:
  167.  
  168. #define neither 0
  169. #define Both 1
  170. #define A 2
  171. #define B 3
  172.  
  173. char lookahead;
  174.  
  175. int match(char c)
  176. {
  177.     if c == lookahead)
  178.     {
  179.         lookahead = getchar();
  180.         return 1;
  181.     }
  182.     else
  183.         return 0;
  184. }
  185.  
  186. int AorB()
  187. {
  188.     int r;
  189.  
  190.     if (match('x'))
  191.     {
  192.         switch (AorB())
  193.         {
  194.             case neither:
  195.                 return neither;
  196.             case A:
  197.                 if (match('y'))
  198.                     return A;
  199.                 else
  200.                     return neither;
  201.             case B:
  202.                 if (match('z'))
  203.                     return B;
  204.                 else
  205.                     return neither;
  206.             case Both: /* omitted */
  207.         }
  208.     }
  209.     else
  210.         return neither;
  211. }
  212.  
  213. Note: This approach is top-down and recursive descent, but not predictive
  214. parsing!  I suppose others have figured this out before. I have no label
  215. to stick upon it. Maybe someone else on the net.
  216.  
  217. Regards,
  218.  
  219. Jan Schramp
  220. --
  221. Jan Schramp, Haagse Hogeschool - Sector Informatica. Louis Couperusplein 19,
  222. 2514 HP  Den Haag, Netherlands. E-mail: jan@si.hhs.nl
  223. -- 
  224. Send compilers articles to compilers@iecc.cambridge.ma.us or
  225. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  226.