LLgen.n 33 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072
  1. .\" $Id$
  2. .\" Run this paper off with
  3. .\" refer [options] -p LLgen.refs LLgen.doc | [n]eqn | tbl | (nt)roff -ms
  4. .if '\*(>.'' \{\
  5. . if '\*(<.'' \{\
  6. . if n .ds >. .
  7. . if n .ds >, ,
  8. . if t .ds <. .
  9. . if t .ds <, ,\
  10. \}\
  11. \}
  12. .cs 5 22u
  13. .ND
  14. .EQ
  15. delim @@
  16. .EN
  17. .TL
  18. LLgen, an extended LL(1) parser generator
  19. .AU
  20. Ceriel J. H. Jacobs
  21. .AI
  22. Dept. of Mathematics and Computer Science
  23. Vrije Universiteit
  24. Amsterdam, The Netherlands
  25. .AB
  26. \fILLgen\fR provides a
  27. tool for generating an efficient recursive descent parser
  28. with no backtrack from
  29. an Extended Context Free syntax.
  30. The \fILLgen\fR
  31. user specifies the syntax, together with code
  32. describing actions associated with the parsing process.
  33. \fILLgen\fR
  34. turns this specification into a number of subroutines that handle the
  35. parsing process.
  36. .PP
  37. The grammar may be ambiguous.
  38. \fILLgen\fR contains both static and dynamic facilities
  39. to resolve these ambiguities.
  40. .PP
  41. The specification can be split into several files, for each of
  42. which \fILLgen\fR generates an output file containing the
  43. corresponding part of the parser.
  44. Furthermore, only output files that differ from their previous
  45. version are updated.
  46. Other output files are not affected in any
  47. way.
  48. This allows the user to recompile only those output files that have
  49. changed.
  50. .PP
  51. The subroutine produced by \fILLgen\fR calls a user supplied routine
  52. that must return the next token. This way, the input to the
  53. parser can be split into single characters or higher level
  54. tokens.
  55. .PP
  56. An error recovery mechanism is generated almost completely
  57. automatically.
  58. It is based on so called \fBdefault choices\fR, which are
  59. implicitly or explicitly specified by the user.
  60. .PP
  61. \fILLgen\fR has succesfully been used to create recognizers for
  62. Pascal, C, and Modula-2.
  63. .AE
  64. .NH
  65. Introduction
  66. .PP
  67. \fILLgen\fR
  68. provides a tool for generating an efficient recursive
  69. descent parser with no backtrack from an Extended Context Free
  70. syntax.
  71. A parser generated by
  72. \fILLgen\fR
  73. will be called
  74. \fILLparse\fR
  75. for the rest of this document.
  76. It is assumed that the reader has some knowledge of LL(1) grammars and
  77. recursive descent parsers.
  78. For a survey on the subject, see reference
  79. .[ (
  80. griffiths
  81. .]).
  82. .PP
  83. Extended LL(1) parsers are an extension of LL(1) parsers. They are
  84. derived from an Extended Context-Free (ECF) syntax instead of a Context-Free
  85. (CF) syntax.
  86. ECF syntax is described in section 2.
  87. Section 3 provides an outline of a
  88. specification as accepted by
  89. \fILLgen\fR and also discusses the lexical conventions of
  90. grammar specification files.
  91. Section 4 provides a description of the way the
  92. \fILLgen\fR
  93. user can associate
  94. actions with the syntax. These actions must be written in the programming
  95. language C,
  96. .[
  97. kernighan ritchie
  98. .]
  99. which also is the target language of \fILLgen\fR.
  100. The error recovery technique is discussed in section 5.
  101. This section also discusses what the user can do about it.
  102. Section 6 discusses
  103. the facilities \fILLgen\fR offers
  104. to resolve ambiguities and conflicts.
  105. \fILLgen\fR offers facilities to resolve them both at parser
  106. generation time and during the execution of \fILLparse\fR.
  107. Section 7 discusses the
  108. \fILLgen\fR
  109. working environment.
  110. It also discusses the lexical analyzer that must be supplied by the
  111. user.
  112. This lexical analyzer must read the input stream and break it
  113. up into basic input items, called \fBtokens\fR for the rest of
  114. this document.
  115. Appendix A gives a summary of the
  116. \fILLgen\fR
  117. input syntax.
  118. Appendix B gives an example.
  119. It is very instructive to compare this example with the one
  120. given in reference
  121. .[ (
  122. yacc
  123. .]).
  124. It demonstrates the struggle \fILLparse\fR and other LL(1)
  125. parsers have with expressions.
  126. Appendix C gives an example of the \fILLgen\fR features
  127. allowing the user to recompile only those output files that
  128. have changed, using the \fImake\fR program.
  129. .[
  130. make
  131. .]
  132. .NH
  133. The Extended Context-Free Syntax
  134. .PP
  135. The extensions of an ECF syntax with respect to an ordinary CF syntax are:
  136. .IP 1. 10
  137. An ECF syntax contains the repetition operator: "N" (N represents a positive
  138. integer).
  139. .IP 2. 10
  140. An ECF syntax contains the closure set operator without and with
  141. upperbound: "*" and "*N".
  142. .IP 3. 10
  143. An ECF syntax contains the positive closure set operator without and with
  144. upperbound: "+" and "+N".
  145. .IP 4. 10
  146. An ECF syntax contains the optional operator: "?", which is a
  147. shorthand for "*1".
  148. .IP 5. 10
  149. An ECF syntax contains parentheses "[" and "]" which can be
  150. used for grouping.
  151. .PP
  152. We can describe the syntax of an ECF syntax with an ECF syntax :
  153. .DS
  154. .ft CW
  155. grammar : rule +
  156. ;
  157. .ft R
  158. .DE
  159. This grammar rule states that a grammar consists of one or more
  160. rules.
  161. .DS
  162. .ft CW
  163. rule : nonterminal ':' productionrule ';'
  164. ;
  165. .ft R
  166. .DE
  167. A rule consists of a left hand side, the nonterminal,
  168. followed by ":",
  169. the \fBproduce symbol\fR, followed by a production rule, followed by a
  170. ";", in\%di\%ca\%ting the end of the rule.
  171. .DS
  172. .ft CW
  173. productionrule : production [ '|' production ]*
  174. ;
  175. .ft R
  176. .DE
  177. A production rule consists of one or
  178. more alternative productions separated by "|". This symbol is called the
  179. \fBalternation symbol\fR.
  180. .DS
  181. .ft CW
  182. production : term *
  183. ;
  184. .ft R
  185. .DE
  186. A production consists of a possibly empty list of terms.
  187. So, empty productions are allowed.
  188. .DS
  189. .ft CW
  190. term : element repeats
  191. ;
  192. .ft R
  193. .DE
  194. A term is an element, possibly with a repeat specification.
  195. .DS
  196. .ft CW
  197. element : LITERAL
  198. | IDENTIFIER
  199. | '[' productionrule ']'
  200. ;
  201. .ft R
  202. .DE
  203. An element can be a LITERAL, which basically is a single character
  204. between apostrophes, it can be an IDENTIFIER, which is either a
  205. nonterminal or a token, and it can be a production rule
  206. between square parentheses.
  207. .DS
  208. .ft CW
  209. repeats : '?'
  210. | [ '*' | '+' ] NUMBER ?
  211. | NUMBER ?
  212. ;
  213. .ft R
  214. .DE
  215. These are the repeat specifications discussed above. Notice that
  216. this specification may be empty.
  217. .PP
  218. The class of ECF languages
  219. is identical with the class of CF languages. However, in many
  220. cases recursive definitions of language features can now be
  221. replaced by iterative ones. This tends to reduce the number of
  222. nonterminals and gives rise to very efficient recursive descent
  223. parsers.
  224. .NH
  225. Grammar Specifications
  226. .PP
  227. The major part of a
  228. \fILLgen\fR
  229. grammar specification consists of an
  230. ECF syntax specification.
  231. Names in this syntax specification refer to either tokens or nonterminal
  232. symbols.
  233. \fILLgen\fR
  234. requires token names to be declared as such. This way it
  235. can be avoided that a typing error in a nonterminal name causes it to
  236. be accepted as a token name. The token declarations will be
  237. discussed later.
  238. A name will be regarded as a nonterminal symbol, unless it is declared
  239. as a token name.
  240. If there is no production rule for a nonterminal symbol, \fILLgen\fR
  241. will complain.
  242. .PP
  243. A grammar specification may also include some C routines,
  244. for instance the lexical analyzer and an error reporting
  245. routine.
  246. Thus, a grammar specification file can contain declarations,
  247. grammar rules and C-code.
  248. .PP
  249. Blanks, tabs and newlines are ignored, but may not appear in names or
  250. keywords.
  251. Comments may appear wherever a name is legal (which is almost
  252. everywhere).
  253. They are enclosed in
  254. /* ... */, as in C. Comments do not nest.
  255. .PP
  256. Names may be of arbitrary length, and can be made up of letters, underscore
  257. "\_" and non-initial digits. Upper and lower case letters are distinct.
  258. Only the first 50 characters are significant.
  259. Notice however, that the names for the tokens will be used by the
  260. C-preprocessor.
  261. The number of significant characters therefore depends on the
  262. underlying C-implementation.
  263. A safe rule is to make the identifiers distinct in the first six
  264. characters, case ignored.
  265. .PP
  266. There are two kinds of tokens:
  267. those that are declared and are denoted by a name,
  268. and literals.
  269. .PP
  270. A literal consists of a character enclosed in apostrophes "'".
  271. The "\e" is an escape character within literals. The following escapes
  272. are recognized :
  273. .TS
  274. center;
  275. l l.
  276. \&'\en' newline
  277. \&'\er' return
  278. \&'\e'' apostrophe "'"
  279. \&'\e\e' backslash "\e"
  280. \&'\et' tab
  281. \&'\eb' backspace
  282. \&'\ef' form feed
  283. \&'\exxx' "xxx" in octal
  284. .TE
  285. .PP
  286. Names representing tokens must be declared before they are used.
  287. This can be done using the "\fB%token\fR" keyword,
  288. by writing
  289. .nf
  290. .ft CW
  291. .sp 1
  292. %token name1, name2, . . . ;
  293. .ft R
  294. .fi
  295. .PP
  296. \fILLparse\fR is designed to recognize special nonterminal
  297. symbols called \fBstart symbols\fR.
  298. \fILLgen\fR allows for more than one start symbol.
  299. Thus, grammars with more than one entry point are accepted.
  300. The start symbols must be declared explicitly using the
  301. "\fB%start\fR" keyword. It can be used whenever a declaration is
  302. legal, f.i.:
  303. .nf
  304. .ft CW
  305. .sp 1
  306. %start LLparse, specification ;
  307. .ft R
  308. .fi
  309. .sp 1
  310. declares "specification" as a start symbol and associates the
  311. identifier "LLparse" with it.
  312. "LLparse" will now be the name of the C-function that must be
  313. called to recognize "specification".
  314. .NH
  315. Actions
  316. .PP
  317. \fILLgen\fR
  318. allows arbitrary insertions of actions within the right hand side
  319. of a production rule in the ECF syntax. An action consists of a number of C
  320. statements, enclosed in the brackets "{" and "}".
  321. .PP
  322. \fILLgen\fR
  323. generates a parsing routine for each rule in the grammar. The actions
  324. supplied by the user are just inserted in the proper place.
  325. There may also be declarations before the statements in the
  326. action, as
  327. the "{" and "}" are copied into the target code along with the
  328. action. The scope of these declarations terminates with the
  329. closing bracket "}" of the action.
  330. .PP
  331. In addition to actions, it is also possible to declare local variables
  332. in the parsing routine, which can then be used in the actions.
  333. Such a declaration consists of a number of C variable declarations,
  334. enclosed in the brackets "{" and "}". It must be placed
  335. right in front of the ":" in the grammar rule.
  336. The scope of these local variables consists of the complete
  337. grammar rule.
  338. .PP
  339. In order to facilitate communication between the actions and
  340. \fILLparse\fR,
  341. the parsing routines can be given C-like parameters. So, for example
  342. .nf
  343. .ft CW
  344. .sp 1
  345. expr(int *pval;) { int fact; } :
  346. /*
  347. * Rule with one parameter, a pointer to an int.
  348. * Parameter specifications are ordinary C declarations.
  349. * One local variable, of type int.
  350. */
  351. factor (&fact) { *pval = fact; }
  352. /*
  353. * factor is another nonterminal symbol.
  354. * One actual parameter is supplied.
  355. * Notice that the parameter passing mechanism is that
  356. * of C.
  357. */
  358. [ '+' factor (&fact) { *pval += fact; } ]*
  359. /*
  360. * remember the '*' means zero or more times
  361. */
  362. ;
  363. .sp 1
  364. .ft R
  365. .fi
  366. is a rule to recognize a number of factors, separated by "+", and
  367. to compute their sum.
  368. .PP
  369. \fILLgen\fR
  370. generates C code, so the parameter passing mechanism is that of
  371. C, as is shown in the example above.
  372. .PP
  373. Actions often manipulate attributes of the token just read.
  374. For instance, when an identifier is read, its name must be
  375. looked up in a symbol table.
  376. Therefore, \fILLgen\fR generates code
  377. such that at a number of places in the grammar rule
  378. it is defined which token has last been read.
  379. After a token, the last token read is this token.
  380. After a "[" or a "|", the last token read is the next token to
  381. be accepted by \fILLparse\fR.
  382. At all other places, it is undefined which token has last been
  383. read.
  384. The last token read is available in the global integer variable
  385. \fILLsymb\fR.
  386. .PP
  387. The user may also specify C-code wherever a \fILLgen\fR-declaration is
  388. legal.
  389. Again, this code must be enclosed in the brackets "{" and "}".
  390. This way, the user can define global declarations and
  391. C-functions.
  392. To avoid name-conflicts with identifiers generated by
  393. \fILLgen\fR, \fILLparse\fR only uses names beginning with
  394. "LL"; the user should avoid such names.
  395. .NH
  396. Error Recovery
  397. .PP
  398. The error recovery technique used by \fILLgen\fR is a
  399. modification of the one presented in reference
  400. .[ (
  401. automatic construction error correcting
  402. .]).
  403. It is based on \fBdefault choices\fR, which just are
  404. what the word says, default choices at
  405. every point in the grammar where there is a
  406. choice.
  407. Thus, in an alternation, one of the productions is marked as a
  408. default choice, and in a term with a non-fixed repetition
  409. specification there will also be a default choice (between
  410. doing the term (once more) and continuing with the rest of the
  411. production in which the term appears).
  412. .PP
  413. When \fILLparse\fR detects an error after having parsed the
  414. string @s@, the default choices enable it to compute one
  415. syntactically correct continuation,
  416. consisting of the tokens @t sub 1~...~t sub n@,
  417. such that @s~t sub 1~...~t sub n@ is a string of tokens that
  418. is a member of the language defined by the grammar.
  419. Notice, that the computation of this continuation must
  420. terminate, which implies that the default choices may not
  421. invoke recursive rules.
  422. .PP
  423. At each point in this continuation, a certain number of other
  424. tokens could also be syntactically correct, f.i. the token
  425. @t@ is syntactically correct at point @t sub i@ in this
  426. continuation, if the string @s~t sub 1~...~t sub i~t~s sub 1@
  427. is a string of the language defined by the grammar for some
  428. string @s sub 1@ and i >= 0.
  429. .PP
  430. The set @T@
  431. containing all these tokens (including @t sub 1 ,~...,~t sub n@) is computed.
  432. Next, \fILLparse\fR discards zero
  433. or more tokens from its input, until a token
  434. @t@ \(mo @T@ is found.
  435. The error is then corrected by inserting i (i >= 0) tokens
  436. @t sub 1~...~t sub i@, such that the string
  437. @s~t sub 1~...~t sub i~t~s sub 1@ is a string of the language
  438. defined by the grammar, for some @s sub 1@.
  439. Then, normal parsing is resumed.
  440. .PP
  441. The above is difficult to implement in a recursive decent
  442. parser, and is not the way \fILLparse\fR does it, but the
  443. effect is the same. In fact, \fILLparse\fR maintains a list
  444. of tokens that may not be discarded, which is adjusted as
  445. \fILLparse\fR proceeds. This list is just a representation
  446. of the set @T@ mentioned
  447. above. When an error occurs, \fILLparse\fR discards tokens until
  448. a token @t@ that is a member of this list is found.
  449. Then, it continues parsing, following the default choices,
  450. inserting tokens along the way, until this token @t@ is legal.
  451. The selection of
  452. the default choices must guarantee that this will always
  453. happen.
  454. .PP
  455. The default choices are explicitly or implicitly
  456. specified by the user.
  457. By default, the default choice in an alternation is the
  458. alternative with the shortest possible terminal production.
  459. The user can select one of the other productions in the
  460. alternation as the default choice by putting the keyword
  461. "\fB%default\fR" in front of it.
  462. .PP
  463. By default, for terms with a repetition count containing "*" or
  464. "?" the default choice is to continue with the rest of the rule
  465. in which the term appears, and
  466. .sp 1
  467. .ft CW
  468. .nf
  469. term+
  470. .fi
  471. .ft R
  472. .sp 1
  473. is treated as
  474. .sp 1
  475. .nf
  476. .ft CW
  477. term term* .
  478. .ft R
  479. .fi
  480. .PP
  481. It is also clear, that it can never be the default choice to do
  482. the term (once more), because this could cause the parser to
  483. loop, inserting tokens forever.
  484. However, when the user does not want the parser to skip
  485. tokens that would not have been skipped if the term
  486. would have been the default choice,
  487. the skipping of such a term can be prevented by
  488. using the keyword "\fB%persistent\fR".
  489. For instance, the rule
  490. .sp 1
  491. .ft CW
  492. .nf
  493. commandlist : command* ;
  494. .fi
  495. .ft R
  496. .sp 1
  497. could be changed to
  498. .sp 1
  499. .ft CW
  500. .nf
  501. commandlist : [ %persistent command ]* ;
  502. .fi
  503. .ft R
  504. .sp 1
  505. The effects of this in case of a syntax error are twofold:
  506. The set @T@ mentioned above will be extended as if "command" were
  507. in the default production, so that fewer tokens will be
  508. skipped.
  509. Also, if the first token that is not skipped is a member of the
  510. subset of @T@ arising from the grammar rule for "command",
  511. \fILLparse\fR will enter that rule.
  512. So, in fact the default choice
  513. is determined dynamically (by \fILLparse\fR).
  514. Again, \fILLgen\fR checks (statically)
  515. that \fILLparse\fR will always terminate, and if not,
  516. \fILLgen\fR will complain.
  517. .PP
  518. An important property of this error recovery method is that,
  519. once a rule is started, it will be finished.
  520. This means that all actions in the rule will be executed
  521. normally, so that the user can be sure that there will be no
  522. inconsistencies in his data structures because of syntax
  523. errors.
  524. Also, as the method is in fact error correcting, the
  525. actions in a rule only have to deal with syntactically correct
  526. input.
  527. .NH
  528. Ambiguities and conflicts
  529. .PP
  530. As \fILLgen\fR generates a recursive descent parser with no backtrack,
  531. it must at all times be able to determine what to do,
  532. based on the current input symbol.
  533. Unfortunately, this cannot be done for all grammars.
  534. Two kinds of conflicts can arise :
  535. .IP 1) 10
  536. the grammar rule is of the form "production1 | production2",
  537. and \fILLparse\fR cannot decide which production to chose.
  538. This we call an \fBalternation conflict\fR.
  539. .IP 2) 10
  540. the grammar rule is of the form "[ productionrule ]...",
  541. where ... specifies a non-fixed repetition count,
  542. and \fILLparse\fR cannot decide whether to
  543. choose "productionrule" once more, or to continue.
  544. This we call a \fBrepetition conflict\fR.
  545. .PP
  546. There can be several causes for conflicts: the grammar may be
  547. ambiguous, or the grammar may require a more complex parser
  548. than \fILLgen\fR can construct.
  549. The conflicts can be examined by inspecting the verbose
  550. (-\fBv\fR) option output file.
  551. The conflicts can be resolved by rewriting the grammar
  552. or by using \fBconflict resolvers\fR.
  553. The mechanism described here is based on the attributed parsing
  554. of reference
  555. .[ (
  556. milton
  557. .]).
  558. .PP
  559. An alternation conflict can be resolved by putting an \fBif condition\fR
  560. in front of the first conflicting production.
  561. It consists of a "\fB%if\fR" followed by a
  562. C-expression between parentheses.
  563. \fILLparse\fR will then evaluate this expression whenever a
  564. token is met at this point on which there is a conflict, so
  565. the conflict will be resolved dynamically.
  566. If the expression evaluates to
  567. non-zero, the first conflicting production is chosen,
  568. otherwise one of the remaining ones is chosen.
  569. .PP
  570. An alternation conflict can also be resolved using the keywords
  571. "\fB%prefer\fR" or "\fB%avoid\fR". "\fB%prefer\fR"
  572. is equivalent in behaviour to
  573. "\fB%if\fR (1)". "\fB%avoid\fR" is equivalent to "\fB%if\fR (0)".
  574. In these cases however, "\fB%prefer\fR" and "\fB%avoid\fR" should be used,
  575. as they resolve the conflict statically and thus
  576. give rise to better C-code.
  577. .PP
  578. A repetition conflict can be resolved by putting a \fBwhile condition\fR
  579. right after the opening parentheses. This while condition
  580. consists of a "\fB%while\fR" followed by a C-expression between
  581. parentheses. Again, \fILLparse\fR will then
  582. evaluate this expression whenever a token is met
  583. at this point on which there is a conflict.
  584. If the expression evaluates to non-zero, the
  585. repeating part is chosen, otherwise the parser continues with
  586. the rest of the rule.
  587. Appendix B will give an example of these features.
  588. .PP
  589. A useful aid in writing conflict resolvers is the "\fB%first\fR" keyword.
  590. It is used to declare a C-macro that forms an expression
  591. returning 1 if the parameter supplied can start a specified
  592. nonterminal, f.i.:
  593. .sp 1
  594. .nf
  595. .ft CW
  596. %first fmac, nonterm ;
  597. .ft R
  598. .sp 1
  599. .fi
  600. declares "fmac" as a macro with one parameter, whose value
  601. is a token number. If the parameter
  602. X can start the nonterminal "nonterm", "fmac(X)" is true,
  603. otherwise it is false.
  604. .NH
  605. The LLgen working environment
  606. .PP
  607. \fILLgen\fR generates a number of files: one for each input
  608. file, and two other files: \fILpars.c\fR and \fILpars.h\fR.
  609. \fILpars.h\fR contains "#-define"s for the tokennames.
  610. \fILpars.c\fR contains the error recovery routines and tables.
  611. Only those output files that differ from their previous version
  612. are updated. See appendix C for a possible application of this
  613. feature.
  614. .PP
  615. The names of the output files are constructed as
  616. follows:
  617. in the input file name, the suffix after the last point is
  618. replaced by a "c". If no point is present in the input file
  619. name, ".c" is appended to it. \fILLgen\fR checks that the
  620. filename constructed this way in fact represents a previous
  621. version, or does not exist already.
  622. .PP
  623. The user must provide some environment to obtain a complete
  624. program.
  625. Routines called \fImain\fR and \fILLmessage\fR must be defined.
  626. Also, a lexical analyzer must be provided.
  627. .PP
  628. The routine \fImain\fR must be defined, as it must be in every
  629. C-program. It should eventually call one of the startsymbol
  630. routines.
  631. .PP
  632. The routine \fILLmessage\fR must accept one
  633. parameter, whose value is a token number, zero or -1.
  634. .br
  635. A zero parameter indicates that the current token (the one in
  636. the external variable \fILLsymb\fR) is deleted.
  637. .br
  638. A -1 parameter indicates that the parser expected end of file, but didn't get
  639. it.
  640. The parser will then skip tokens until end of file is detected.
  641. .br
  642. A parameter that is a token number (a positive parameter)
  643. indicates that this
  644. token is to be inserted in front of the token currently in
  645. \fILLsymb\fR.
  646. The user can give the token the proper attributes.
  647. Also, the user must take care, that the token currently in
  648. \fILLsymb\fR is again returned by the \fBnext\fR call to the
  649. lexical analyzer, with the proper attributes.
  650. So, the lexical analyzer must have a facility to push back one
  651. token.
  652. .PP
  653. The user may also supply his own error recovery routines, or handle
  654. errors differently. For this purpose, the name of a routine to be called
  655. when an error occurs may be declared using the keyword \fB%onerror\fR.
  656. This routine takes two parameters.
  657. The first one is either the token number of the
  658. token expected, or 0. In the last case, the error occurred at a choice.
  659. In both cases, the routine must ensure that the next call to the lexical
  660. analyser returns the token that replaces the current one. Of course,
  661. that could well be the current one, in which case
  662. .I LLparse
  663. recovers from the error.
  664. The second parameter contains a list of tokens that are not skipped at the
  665. error point. The list is in the form of a null-terminated array of integers,
  666. whose address is passed.
  667. .PP
  668. The user must supply a lexical analyzer to read the input stream and
  669. break it up into tokens, which are passed to
  670. .I LLparse.
  671. It should be an integer valued function, returning the token number.
  672. The name of this function can be declared using the
  673. "\fB%lexical\fR" keyword.
  674. This keyword can be used wherever a declaration is legal and may appear
  675. only once in the grammar specification, f.i.:
  676. .sp 1
  677. .nf
  678. .ft CW
  679. %lexical scanner ;
  680. .ft R
  681. .fi
  682. .sp 1
  683. declares "scanner" as the name of the lexical analyzer.
  684. The default name for the lexical analyzer is "yylex".
  685. The reason for this funny name is that a useful tool for constructing
  686. lexical analyzers is the
  687. .I Lex
  688. program,
  689. .[
  690. lex
  691. .]
  692. which generates a routine of that name.
  693. .PP
  694. The token numbers are chosen by \fILLgen\fR.
  695. The token number for a literal
  696. is the numerical value of the character in the local character set.
  697. If the tokens have a name,
  698. the "#\ define" mechanism of C is used to give them a value and
  699. to allow the lexical analyzer to return their token numbers symbolically.
  700. These "#\ define"s are collected in the file \fILpars.h\fR which
  701. can be "#\ include"d in any file that needs the token-names.
  702. The maximum token number chosen is defined in the macro \fILL_MAXTOKNO\fP.
  703. .PP
  704. The lexical analyzer must signal the end
  705. of input to \fILLparse\fR
  706. by returning a number less than or equal to zero.
  707. .NH
  708. Programs with more than one parser
  709. .PP
  710. \fILLgen\fR offers a simple facility for having more than one parser in
  711. a program: in this case, the user can change the names of global procedures,
  712. variables, etc, by giving a different prefix, like this:
  713. .sp 1
  714. .nf
  715. .ft CW
  716. %prefix XX ;
  717. .ft R
  718. .fi
  719. .sp 1
  720. The effect of this is that all global names start with XX instead of LL, for
  721. the parser that has this prefix. This holds for the variables \fILLsymb\fP,
  722. which now is called \fIXXsymb\fP, for the routine \fILLmessage\fP,
  723. which must now be called \fIXXmessage\fP, and for the macro \fILL_MAXTOKNO\fP,
  724. which is now called \fIXX_MAXTOKNO\fP.
  725. \fILL.output\fP is now \fIXX.output\fP, and \fILpars.c\fP and \fILpars.h\fP
  726. are now called \fIXXpars.c\fP and \fIXXpars.h\fP.
  727. .bp
  728. .SH
  729. References
  730. .[
  731. $LIST$
  732. .]
  733. .bp
  734. .SH
  735. Appendix A : LLgen Input Syntax
  736. .PP
  737. This appendix has a description of the \fILLgen\fR input syntax,
  738. as a \fILLgen\fR specification. As a matter of fact, the current
  739. version of \fILLgen\fR is written with \fILLgen\fR.
  740. .nf
  741. .ft CW
  742. .sp 2
  743. /*
  744. * First the declarations of the terminals
  745. * The order is not important
  746. */
  747. %token IDENTIFIER; /* terminal or nonterminal name */
  748. %token NUMBER;
  749. %token LITERAL;
  750. /*
  751. * Reserved words
  752. */
  753. %token TOKEN; /* %token */
  754. %token START; /* %start */
  755. %token PERSISTENT; /* %persistent */
  756. %token IF; /* %if */
  757. %token WHILE; /* %while */
  758. %token AVOID; /* %avoid */
  759. %token PREFER; /* %prefer */
  760. %token DEFAULT; /* %default */
  761. %token LEXICAL; /* %lexical */
  762. %token PREFIX; /* %prefix */
  763. %token ONERROR; /* %onerror */
  764. %token FIRST; /* %first */
  765. /*
  766. * Declare LLparse to be a C-routine that recognizes "specification"
  767. */
  768. %start LLparse, specification;
  769. specification
  770. : declaration*
  771. ;
  772. declaration
  773. : START
  774. IDENTIFIER ',' IDENTIFIER
  775. ';'
  776. | '{'
  777. /* Read C-declaration here */
  778. '}'
  779. | TOKEN
  780. IDENTIFIER
  781. [ ',' IDENTIFIER ]*
  782. ';'
  783. | FIRST
  784. IDENTIFIER ',' IDENTIFIER
  785. ';'
  786. | LEXICAL
  787. IDENTIFIER
  788. ';'
  789. | PREFIX
  790. IDENTIFIER
  791. ';'
  792. | ONERROR
  793. IDENTIFIER
  794. ';'
  795. | rule
  796. ;
  797. rule : IDENTIFIER parameters? ldecl?
  798. ':' productions
  799. ';'
  800. ;
  801. ldecl : '{'
  802. /* Read C-declaration here */
  803. '}'
  804. ;
  805. productions
  806. : simpleproduction
  807. [ '|' simpleproduction ]*
  808. ;
  809. simpleproduction
  810. : DEFAULT?
  811. [ IF '(' /* Read C-expression here */ ')'
  812. | PREFER
  813. | AVOID
  814. ]?
  815. [ element repeats ]*
  816. ;
  817. element : '{'
  818. /* Read action here */
  819. '}'
  820. | '[' [ WHILE '(' /* Read C-expression here */ ')' ]?
  821. PERSISTENT?
  822. productions
  823. ']'
  824. | LITERAL
  825. | IDENTIFIER parameters?
  826. ;
  827. parameters
  828. : '(' /* Read C-parameters here */ ')'
  829. ;
  830. repeats : /* empty */
  831. | [ '*' | '+' ] NUMBER?
  832. | NUMBER
  833. | '?'
  834. ;
  835. .fi
  836. .ft R
  837. .bp
  838. .SH
  839. Appendix B : An example
  840. .PP
  841. This example gives the complete \fILLgen\fR specification of a simple
  842. desk calculator. It has 26 registers, labeled "a" through "z",
  843. and accepts arithmetic expressions made up of the C operators
  844. +, -, *, /, %, &, and |, with their usual priorities.
  845. The value of the expression is
  846. printed. As in C, an integer that begins with 0 is assumed to
  847. be octal; otherwise it is assumed to be decimal.
  848. .PP
  849. Although the example is short and not very complicated, it
  850. demonstrates the use of if and while conditions. In
  851. the example they are in fact used to reduce the number of
  852. nonterminals, and to reduce the overhead due to the recursion
  853. that would be involved in parsing an expression with an
  854. ordinary recursive descent parser. In an ordinary LL(1)
  855. grammar there would be one nonterminal for each operator
  856. priority. The example shows how we can do it all with one
  857. nonterminal, no matter how many priority levels there are.
  858. .sp 1
  859. .nf
  860. .ft CW
  861. {
  862. #include <stdio.h>
  863. #include <ctype.h>
  864. #define MAXPRIO 5
  865. #define prio(op) (ptab[op])
  866. struct token {
  867. int t_tokno; /* token number */
  868. int t_tval; /* Its attribute */
  869. } stok = { 0,0 }, tok;
  870. int nerrors = 0;
  871. int regs[26]; /* Space for the registers */
  872. int ptab[128]; /* Attribute table */
  873. struct token
  874. nexttok() { /* Read next token and return it */
  875. register c;
  876. struct token new;
  877. while ((c = getchar()) == ' ' || c == '\et') { /* nothing */ }
  878. if (isdigit(c)) new.t_tokno = DIGIT;
  879. else if (islower(c)) new.t_tokno = IDENT;
  880. else new.t_tokno = c;
  881. if (c >= 0) new.t_tval = ptab[c];
  882. return new;
  883. } }
  884. %token DIGIT, IDENT;
  885. %start parse, list;
  886. list : stat* ;
  887. stat { int ident, val; } :
  888. %if (stok = nexttok(),
  889. stok.t_tokno == '=')
  890. /* The conflict is resolved by looking one further
  891. * token ahead. The grammar is LL(2)
  892. */
  893. IDENT
  894. { ident = tok.t_tval; }
  895. '=' expr(1,&val) '\en'
  896. { if (!nerrors) regs[ident] = val; }
  897. | expr(1,&val) '\en'
  898. { if (!nerrors) printf("%d\en",val); }
  899. | '\en'
  900. ;
  901. expr(int level, int *val;) { int expr; } :
  902. factor(val)
  903. [ %while (prio(tok.t_tokno) >= level)
  904. /* Swallow operators as long as their priority is
  905. * larger than or equal to the level of this invocation
  906. */
  907. '+' expr(prio('+')+1,&expr)
  908. { *val += expr; }
  909. /* This states that '+' groups left to right. If it
  910. * should group right to left, the rule should read:
  911. * '+' expr(prio('+'),&expr)
  912. */
  913. | '-' expr(prio('-')+1,&expr)
  914. { *val -= expr; }
  915. | '*' expr(prio('*')+1,&expr)
  916. { *val *= expr; }
  917. | '/' expr(prio('/')+1,&expr)
  918. { *val /= expr; }
  919. | '%' expr(prio('%')+1,&expr)
  920. { *val %= expr; }
  921. | '&' expr(prio('&')+1,&expr)
  922. { *val &= expr; }
  923. | '|' expr(prio('|')+1,&expr)
  924. { *val |= expr; }
  925. ]*
  926. /* Notice the "*" here. It is important.
  927. */
  928. ;
  929. factor(int *val;):
  930. '(' expr(1,val) ')'
  931. | '-' expr(MAXPRIO+1,val)
  932. { *val = -*val; }
  933. | number(val)
  934. | IDENT
  935. { *val = regs[tok.t_tval]; }
  936. ;
  937. number(int *val;) { int base; }
  938. : DIGIT
  939. { base = (*val=tok.t_tval)==0?8:10; }
  940. [ DIGIT
  941. { *val = base * *val + tok.t_tval; }
  942. ]* ;
  943. %lexical scanner ;
  944. {
  945. scanner() {
  946. if (stok.t_tokno) { /* a token has been inserted or read ahead */
  947. tok = stok;
  948. stok.t_tokno = 0;
  949. return tok.t_tokno;
  950. }
  951. if (nerrors && tok.t_tokno == '\en') {
  952. printf("ERROR\en");
  953. nerrors = 0;
  954. }
  955. tok = nexttok();
  956. return tok.t_tokno;
  957. }
  958. LLmessage(insertedtok) {
  959. nerrors++;
  960. if (insertedtok) { /* token inserted, save old token */
  961. stok = tok;
  962. tok.t_tval = 0;
  963. if (insertedtok < 128) tok.t_tval = ptab[insertedtok];
  964. }
  965. }
  966. main() {
  967. register *p;
  968. for (p = ptab; p < &ptab[128]; p++) *p = 0;
  969. /* for letters, their attribute is their index in the regs array */
  970. for (p = &ptab['a']; p <= &ptab['z']; p++) *p = p - &ptab['a'];
  971. /* for digits, their attribute is their value */
  972. for (p = &ptab['0']; p <= &ptab['9']; p++) *p = p - &ptab['0'];
  973. /* for operators, their attribute is their priority */
  974. ptab['*'] = 4;
  975. ptab['/'] = 4;
  976. ptab['%'] = 4;
  977. ptab['+'] = 3;
  978. ptab['-'] = 3;
  979. ptab['&'] = 2;
  980. ptab['|'] = 1;
  981. parse();
  982. exit(nerrors);
  983. } }
  984. .fi
  985. .ft R
  986. .bp
  987. .SH
  988. Appendix C. How to use \fILLgen\fR.
  989. .PP
  990. This appendix demonstrates how \fILLgen\fR can be used in
  991. combination with the \fImake\fR program, to make effective use
  992. of the \fILLgen\fR-feature that it only changes output files
  993. when neccessary. \fIMake\fR uses a "makefile", which
  994. is a file containing dependencies and associated commands.
  995. A dependency usually indicates that some files depend on other
  996. files. When a file depends on another file and is older than
  997. that other file, the commands associated with the dependency
  998. are executed.
  999. .PP
  1000. So, \fImake\fR seems just the program that we always wanted.
  1001. However, it
  1002. is not very good in handling programs that generate more than
  1003. one file.
  1004. As usual, there is a way around this problem.
  1005. A sample makefile follows:
  1006. .sp 1
  1007. .ft CW
  1008. .nf
  1009. # The grammar exists of the files decl.g, stat.g and expr.g.
  1010. # The ".o"-files are the result of a C-compilation.
  1011. GFILES = decl.g stat.g expr.g
  1012. OFILES = decl.o stat.o expr.o Lpars.o
  1013. LLOPT =
  1014. # As make does'nt handle programs that generate more than one
  1015. # file well, we just don't tell make about it.
  1016. # We just create a dummy file, and touch it whenever LLgen is
  1017. # executed. This way, the dummy in fact depends on the grammar
  1018. # files.
  1019. # Then, we execute make again, to do the C-compilations and
  1020. # such.
  1021. all: dummy
  1022. make parser
  1023. dummy: $(GFILES)
  1024. LLgen $(LLOPT) $(GFILES)
  1025. touch dummy
  1026. parser: $(OFILES)
  1027. $(CC) -o parser $(LDFLAGS) $(OFILES)
  1028. # Some dependencies without actions :
  1029. # make already knows what to do about them
  1030. Lpars.o: Lpars.h
  1031. stat.o: Lpars.h
  1032. decl.o: Lpars.h
  1033. expr.o: Lpars.h
  1034. .fi
  1035. .ft R