logo

oasis-root

Compiled tree of Oasis Linux based on own branch at <https://hacktivis.me/git/oasis/> git clone https://anongit.hacktivis.me/git/oasis-root.git

yacc.1p (49732B)


  1. '\" et
  2. .TH YACC "1P" 2017 "IEEE/The Open Group" "POSIX Programmer's Manual"
  3. .\"
  4. .SH PROLOG
  5. This manual page is part of the POSIX Programmer's Manual.
  6. The Linux implementation of this interface may differ (consult
  7. the corresponding Linux manual page for details of Linux behavior),
  8. or the interface may not be implemented on Linux.
  9. .\"
  10. .SH NAME
  11. yacc
  12. \(em yet another compiler compiler (\fBDEVELOPMENT\fP)
  13. .SH SYNOPSIS
  14. .LP
  15. .nf
  16. yacc \fB[\fR-dltv\fB] [\fR-b \fIfile_prefix\fB] [\fR-p \fIsym_prefix\fB]\fI grammar\fR
  17. .fi
  18. .SH DESCRIPTION
  19. The
  20. .IR yacc
  21. utility shall read a description of a context-free grammar in
  22. .IR grammar
  23. and write C source code, conforming to the ISO\ C standard, to a code file,
  24. and optionally header information into a header file, in the current
  25. directory. The generated source code shall not depend on any undefined,
  26. unspecified, or implementation-defined behavior, except in cases where
  27. it is copied directly from the supplied grammar, or in cases that are
  28. documented by the implementation. The C code shall define a function
  29. and related routines and macros for an automaton that executes a parsing
  30. algorithm meeting the requirements in
  31. .IR "Algorithms".
  32. .P
  33. The form and meaning of the grammar are described in the EXTENDED
  34. DESCRIPTION section.
  35. .P
  36. The C source code and header file shall be produced in a form suitable
  37. as input for the C compiler (see
  38. .IR "\fIc99\fR\^").
  39. .SH OPTIONS
  40. The
  41. .IR yacc
  42. utility shall conform to the Base Definitions volume of POSIX.1\(hy2017,
  43. .IR "Section 12.2" ", " "Utility Syntax Guidelines",
  44. except for Guideline 9.
  45. .P
  46. The following options shall be supported:
  47. .IP "\fB\-b\ \fIfile_prefix\fR" 10
  48. Use
  49. .IR file_prefix
  50. instead of
  51. .BR y
  52. as the prefix for all output filenames. The code file
  53. .BR y.tab.c ,
  54. the header file
  55. .BR y.tab.h
  56. (created when
  57. .BR \-d
  58. is specified), and the description file
  59. .BR y.output
  60. (created when
  61. .BR \-v
  62. is specified), shall be changed to
  63. .IR file_prefix \c
  64. .BR .tab.c ,
  65. .IR file_prefix \c
  66. .BR .tab.h ,
  67. and
  68. .IR file_prefix \c
  69. .BR .output ,
  70. respectively.
  71. .IP "\fB\-d\fP" 10
  72. Write the header file; by default only the code file is written. See
  73. the OUTPUT FILES section.
  74. .IP "\fB\-l\fP" 10
  75. Produce a code file that does not contain any
  76. .BR #line
  77. constructs. If this option is not present, it is unspecified whether
  78. the code file or header file contains
  79. .BR #line
  80. directives. This should only be used after the grammar and the
  81. associated actions are fully debugged.
  82. .IP "\fB\-p\ \fIsym_prefix\fR" 10
  83. .br
  84. Use
  85. .IR sym_prefix
  86. instead of
  87. .BR yy
  88. as the prefix for all external names produced by
  89. .IR yacc .
  90. The names affected shall include the functions
  91. \fIyyparse\fR(),
  92. \fIyylex\fR(),
  93. and
  94. \fIyyerror\fR(),
  95. and the variables
  96. .IR yylval ,
  97. .IR yychar ,
  98. and
  99. .IR yydebug .
  100. (In the remainder of this section, the six symbols cited are referenced
  101. using their default names only as a notational convenience.) Local
  102. names may also be affected by the
  103. .BR \-p
  104. option; however, the
  105. .BR \-p
  106. option shall not affect
  107. .BR #define
  108. symbols generated by
  109. .IR yacc .
  110. .IP "\fB\-t\fP" 10
  111. Modify conditional compilation directives to permit compilation of
  112. debugging code in the code file. Runtime debugging statements shall
  113. always be contained in the code file, but by default conditional
  114. compilation directives prevent their compilation.
  115. .IP "\fB\-v\fP" 10
  116. Write a file containing a description of the parser and a report of
  117. conflicts generated by ambiguities in the grammar.
  118. .br
  119. .SH OPERANDS
  120. The following operand is required:
  121. .IP "\fIgrammar\fR" 10
  122. A pathname of a file containing instructions, hereafter called
  123. .IR grammar ,
  124. for which a parser is to be created. The format for the grammar is
  125. described in the EXTENDED DESCRIPTION section.
  126. .SH STDIN
  127. Not used.
  128. .SH "INPUT FILES"
  129. The file
  130. .IR grammar
  131. shall be a text file formatted as specified in the EXTENDED DESCRIPTION
  132. section.
  133. .SH "ENVIRONMENT VARIABLES"
  134. The following environment variables shall affect the execution of
  135. .IR yacc :
  136. .IP "\fILANG\fP" 10
  137. Provide a default value for the internationalization variables that are
  138. unset or null. (See the Base Definitions volume of POSIX.1\(hy2017,
  139. .IR "Section 8.2" ", " "Internationalization Variables"
  140. for the precedence of internationalization variables used to determine
  141. the values of locale categories.)
  142. .IP "\fILC_ALL\fP" 10
  143. If set to a non-empty string value, override the values of all the
  144. other internationalization variables.
  145. .IP "\fILC_CTYPE\fP" 10
  146. Determine the locale for the interpretation of sequences of bytes of
  147. text data as characters (for example, single-byte as opposed to
  148. multi-byte characters in arguments and input files).
  149. .IP "\fILC_MESSAGES\fP" 10
  150. .br
  151. Determine the locale that should be used to affect the format and
  152. contents of diagnostic messages written to standard error.
  153. .IP "\fINLSPATH\fP" 10
  154. Determine the location of message catalogs for the processing of
  155. .IR LC_MESSAGES .
  156. .P
  157. The
  158. .IR LANG
  159. and
  160. .IR LC_*
  161. variables affect the execution of the
  162. .IR yacc
  163. utility as stated. The
  164. \fImain\fR()
  165. function defined in
  166. .IR "Yacc Library"
  167. shall call:
  168. .sp
  169. .RS 4
  170. .nf
  171. setlocale(LC_ALL, "")
  172. .fi
  173. .P
  174. .RE
  175. .P
  176. and thus the program generated by
  177. .IR yacc
  178. shall also be affected by the contents of these variables at runtime.
  179. .SH "ASYNCHRONOUS EVENTS"
  180. Default.
  181. .SH STDOUT
  182. Not used.
  183. .SH STDERR
  184. If shift/reduce or reduce/reduce conflicts are detected in
  185. .IR grammar ,
  186. .IR yacc
  187. shall write a report of those conflicts to the standard error in an
  188. unspecified format.
  189. .P
  190. Standard error shall also be used for diagnostic messages.
  191. .SH "OUTPUT FILES"
  192. The code file, the header file, and the description file shall be text
  193. files. All are described in the following sections.
  194. .SS "Code File"
  195. .P
  196. This file shall contain the C source code for the
  197. \fIyyparse\fR()
  198. function. It shall contain code for the various semantic actions with
  199. macro substitution performed on them as described in the EXTENDED
  200. DESCRIPTION section. It also shall contain a copy of the
  201. .BR #define
  202. statements in the header file. If a
  203. .BR %union
  204. declaration is used, the declaration for YYSTYPE shall also be included
  205. in this file.
  206. .SS "Header File"
  207. .P
  208. The header file shall contain
  209. .BR #define
  210. statements that associate the token numbers with the token names. This
  211. allows source files other than the code file to access the token
  212. codes. If a
  213. .BR %union
  214. declaration is used, the declaration for YYSTYPE and an
  215. .IR "extern YYSTYPE yylval"
  216. declaration shall also be included in this file.
  217. .SS "Description File"
  218. .P
  219. The description file shall be a text file containing a description of
  220. the state machine corresponding to the parser, using an unspecified
  221. format. Limits for internal tables (see
  222. .IR "Limits")
  223. shall also be reported, in an implementation-defined manner. (Some
  224. implementations may use dynamic allocation techniques and have no
  225. specific limit values to report.)
  226. .SH "EXTENDED DESCRIPTION"
  227. The
  228. .IR yacc
  229. command accepts a language that is used to define a grammar for a
  230. target language to be parsed by the tables and code generated by
  231. .IR yacc .
  232. The language accepted by
  233. .IR yacc
  234. as a grammar for the target language is described below using the
  235. .IR yacc
  236. input language itself.
  237. .P
  238. The input
  239. .IR grammar
  240. includes rules describing the input structure of the target language
  241. and code to be invoked when these rules are recognized to provide the
  242. associated semantic action. The code to be executed shall appear as bodies
  243. of text that are intended to be C-language code. These bodies of text
  244. shall not contain C-language trigraphs. The C-language inclusions are
  245. presumed to form a correct function when processed by
  246. .IR yacc
  247. into its output files. The code included in this way shall be executed
  248. during the recognition of the target language.
  249. .P
  250. Given a grammar, the
  251. .IR yacc
  252. utility generates the files described in the OUTPUT FILES section. The
  253. code file can be compiled and linked using
  254. .IR c99 .
  255. If the declaration and programs sections of the grammar file did not
  256. include definitions of
  257. \fImain\fR(),
  258. \fIyylex\fR(),
  259. and
  260. \fIyyerror\fR(),
  261. the compiled output requires linking with externally supplied versions
  262. of those functions. Default versions of
  263. \fImain\fR()
  264. and
  265. \fIyyerror\fR()
  266. are supplied in the
  267. .IR yacc
  268. library and can be linked in by using the
  269. .BR "\-l\ y"
  270. operand to
  271. .IR c99 .
  272. The
  273. .IR yacc
  274. library interfaces need not support interfaces with other than the
  275. default
  276. .BR yy
  277. symbol prefix. The application provides the lexical analyzer function,
  278. \fIyylex\fR();
  279. the
  280. .IR lex
  281. utility is specifically designed to generate such a routine.
  282. .SS "Input Language"
  283. .P
  284. The application shall ensure that every specification file consists of
  285. three sections in order:
  286. .IR declarations ,
  287. .IR "grammar rules" ,
  288. and
  289. .IR programs ,
  290. separated by double
  291. <percent-sign>
  292. characters (\c
  293. .BR \(dq%%\(dq ).
  294. The declarations and programs sections can be empty. If the latter is
  295. empty, the preceding
  296. .BR \(dq%%\(dq
  297. mark separating it from the rules section can be omitted.
  298. .P
  299. The input is free form text following the structure of the grammar
  300. defined below.
  301. .SS "Lexical Structure of the Grammar"
  302. .P
  303. The
  304. <blank>,
  305. <newline>,
  306. and
  307. <form-feed>
  308. character shall be ignored, except that the application shall ensure that
  309. they do not appear in names or multi-character reserved symbols. Comments
  310. shall be enclosed in
  311. .BR \(dq/*\ ...\ */\(dq ,
  312. and can appear wherever a name is valid.
  313. .P
  314. Names are of arbitrary length, made up of letters, periods (\c
  315. .BR '.' ),
  316. underscores (\c
  317. .BR '_' ),
  318. and non-initial digits. Uppercase and lowercase letters are distinct.
  319. Conforming applications shall not use names beginning in
  320. .BR yy
  321. or
  322. .BR YY
  323. since the
  324. .IR yacc
  325. parser uses such names. Many of the names appear in the final output
  326. of
  327. .IR yacc ,
  328. and thus they should be chosen to conform with any additional rules
  329. created by the C compiler to be used. In particular they appear in
  330. .BR #define
  331. statements.
  332. .P
  333. A literal shall consist of a single character enclosed in single-quote
  334. characters. All of the escape sequences supported for character constants
  335. by the ISO\ C standard shall be supported by
  336. .IR yacc .
  337. .P
  338. The relationship with the lexical analyzer is discussed in detail below.
  339. .P
  340. The application shall ensure that the NUL character is not used in
  341. grammar rules or literals.
  342. .SS "Declarations Section"
  343. .P
  344. The declarations section is used to define the symbols used to define
  345. the target language and their relationship with each other. In
  346. particular, much of the additional information required to resolve
  347. ambiguities in the context-free grammar for the target language is
  348. provided here.
  349. .P
  350. Usually
  351. .IR yacc
  352. assigns the relationship between the symbolic names it generates and
  353. their underlying numeric value. The declarations section makes it
  354. possible to control the assignment of these values.
  355. .P
  356. It is also possible to keep semantic information associated with the
  357. tokens currently on the parse stack in a user-defined C-language
  358. .BR union ,
  359. if the members of the union are associated with the various names in
  360. the grammar. The declarations section provides for this as well.
  361. .P
  362. The first group of declarators below all take a list of names as
  363. arguments. That list can optionally be preceded by the name of a C
  364. union member (called a
  365. .IR tag
  366. below) appearing within
  367. .BR '<'
  368. and
  369. .BR '>' .
  370. (As an exception to the typographical conventions of the rest of this volume of POSIX.1\(hy2017,
  371. in this case <\fItag\fP> does not represent a metavariable, but the
  372. literal angle bracket characters surrounding a symbol.) The use of
  373. .IR tag
  374. specifies that the tokens named on this line shall be of the same C
  375. type as the union member referenced by
  376. .IR tag .
  377. This is discussed in more detail below.
  378. .P
  379. For lists used to define tokens, the first appearance of a given token
  380. can be followed by a positive integer (as a string of decimal digits).
  381. If this is done, the underlying value assigned to it for lexical
  382. purposes shall be taken to be that number.
  383. .P
  384. The following declares
  385. .IR name
  386. to be a token:
  387. .sp
  388. .RS 4
  389. .nf
  390. %token \fB[\fR<\fItag\fR>\fB] \fIname \fB[\fInumber\fB] [\fIname \fB[\fInumber\fB]]\fR...
  391. .fi
  392. .P
  393. .RE
  394. .P
  395. If
  396. .IR tag
  397. is present, the C type for all tokens on this line shall be declared to
  398. be the type referenced by
  399. .IR tag .
  400. If a positive integer,
  401. .IR number ,
  402. follows a
  403. .IR name ,
  404. that value shall be assigned to the token.
  405. .P
  406. The following declares
  407. .IR name
  408. to be a token, and assigns precedence to it:
  409. .sp
  410. .RS 4
  411. .nf
  412. %left \fB[\fR<\fItag\fR>\fB] \fIname \fB[\fInumber\fB] [\fIname \fB[\fInumber\fB]]\fR...
  413. %right \fB[\fR<\fItag\fR>\fB] \fIname \fB[\fInumber\fB] [\fIname \fB[\fInumber\fB]]\fR...
  414. .fi
  415. .P
  416. .RE
  417. .P
  418. One or more lines, each beginning with one of these symbols, can appear
  419. in this section. All tokens on the same line have the same precedence
  420. level and associativity; the lines are in order of increasing
  421. precedence or binding strength.
  422. .BR %left
  423. denotes that the operators on that line are left associative, and
  424. .BR %right
  425. similarly denotes right associative operators. If
  426. .IR tag
  427. is present, it shall declare a C type for
  428. .IR name s
  429. as described for
  430. .BR %token .
  431. .P
  432. The following declares
  433. .IR name
  434. to be a token, and indicates that this cannot be used associatively:
  435. .sp
  436. .RS 4
  437. .nf
  438. %nonassoc \fB[\fR<\fItag\fR>\fB] \fIname \fB[\fInumber\fB] [\fIname \fB[\fInumber\fB]]\fR...
  439. .fi
  440. .P
  441. .RE
  442. .P
  443. If the parser encounters associative use of this token it reports an
  444. error. If
  445. .IR tag
  446. is present, it shall declare a C type for
  447. .IR name s
  448. as described for
  449. .BR %token .
  450. .P
  451. The following declares that union member
  452. .IR name s
  453. are non-terminals, and thus it is required to have a
  454. .IR tag
  455. field at its beginning:
  456. .sp
  457. .RS 4
  458. .nf
  459. %type <\fItag\fR> \fIname\fR...
  460. .fi
  461. .P
  462. .RE
  463. .P
  464. Because it deals with non-terminals only, assigning a token number or
  465. using a literal is also prohibited. If this construct is present,
  466. .IR yacc
  467. shall perform type checking; if this construct is not present, the
  468. parse stack shall hold only the
  469. .BR int
  470. type.
  471. .P
  472. Every name used in
  473. .IR grammar
  474. not defined by a
  475. .BR %token ,
  476. .BR %left ,
  477. .BR %right ,
  478. or
  479. .BR %nonassoc
  480. declaration is assumed to represent a non-terminal symbol. The
  481. .IR yacc
  482. utility shall report an error for any non-terminal symbol that does not
  483. appear on the left side of at least one grammar rule.
  484. .P
  485. Once the type, precedence, or token number of a name is specified, it
  486. shall not be changed. If the first declaration of a token does not
  487. assign a token number,
  488. .IR yacc
  489. shall assign a token number. Once this assignment is made, the token
  490. number shall not be changed by explicit assignment.
  491. .P
  492. The following declarators do not follow the previous pattern.
  493. .P
  494. The following declares the non-terminal
  495. .IR name
  496. to be the
  497. .IR "start symbol" ,
  498. which represents the largest, most general structure described by the
  499. grammar rules:
  500. .sp
  501. .RS 4
  502. .nf
  503. %start \fIname\fR
  504. .fi
  505. .P
  506. .RE
  507. .P
  508. By default, it is the left-hand side of the first grammar rule; this
  509. default can be overridden with this declaration.
  510. .P
  511. The following declares the
  512. .IR yacc
  513. value stack to be a union of the various types of values desired.
  514. .sp
  515. .RS 4
  516. .nf
  517. %union { \fIbody of union\fR (\fIin C\fR) }
  518. .fi
  519. .P
  520. .RE
  521. .P
  522. The body of the union shall not contain unbalanced curly brace
  523. preprocessing tokens.
  524. .P
  525. By default, the values returned by actions (see below) and the lexical
  526. analyzer shall be of type
  527. .BR int .
  528. The
  529. .IR yacc
  530. utility keeps track of types, and it shall insert corresponding union
  531. member names in order to perform strict type checking of the resulting
  532. parser.
  533. .P
  534. Alternatively, given that at least one <\fItag\fP> construct is used,
  535. the union can be declared in a header file (which shall be included in
  536. the declarations section by using a
  537. .BR #include
  538. construct within
  539. .BR %{
  540. and
  541. .BR %} ),
  542. and a
  543. .BR typedef
  544. used to define the symbol YYSTYPE to represent this union. The effect
  545. of
  546. .BR %union
  547. is to provide the declaration of YYSTYPE directly from the
  548. .IR yacc
  549. input.
  550. .P
  551. C-language declarations and definitions can appear in the declarations
  552. section, enclosed by the following marks:
  553. .sp
  554. .RS 4
  555. .nf
  556. %{ ... %}
  557. .fi
  558. .P
  559. .RE
  560. .P
  561. These statements shall be copied into the code file, and have global
  562. scope within it so that they can be used in the rules and program
  563. sections. The statements shall not contain
  564. .BR \(dq%}\(dq
  565. outside a comment, string literal, or multi-character constant.
  566. .P
  567. The application shall ensure that the declarations section is
  568. terminated by the token
  569. .BR %% .
  570. .SS "Grammar Rules in yacc"
  571. .P
  572. The rules section defines the context-free grammar to be accepted by
  573. the function
  574. .IR yacc
  575. generates, and associates with those rules C-language actions and
  576. additional precedence information. The grammar is described below, and
  577. a formal definition follows.
  578. .P
  579. The rules section is comprised of one or more grammar rules. A grammar
  580. rule has the form:
  581. .sp
  582. .RS 4
  583. .nf
  584. A : BODY ;
  585. .fi
  586. .P
  587. .RE
  588. .P
  589. The symbol
  590. .BR A
  591. represents a non-terminal name, and
  592. .BR BODY
  593. represents a sequence of zero or more
  594. .IR name s,
  595. .IR literal s,
  596. and
  597. .IR "semantic action" s
  598. that can then be followed by optional
  599. .IR "precedence rule" s.
  600. Only the names and literals participate in the formation of the
  601. grammar; the semantic actions and precedence rules are used in other
  602. ways. The
  603. <colon>
  604. and the
  605. <semicolon>
  606. are
  607. .IR yacc
  608. punctuation. If there are several successive grammar rules with the
  609. same left-hand side, the
  610. <vertical-line>
  611. (\c
  612. .BR '|' )
  613. can be used to avoid rewriting the left-hand side; in this case the
  614. <semicolon>
  615. appears only after the last rule. The BODY part can be empty
  616. (or empty of names and literals) to indicate that the non-terminal
  617. symbol matches the empty string.
  618. .P
  619. The
  620. .IR yacc
  621. utility assigns a unique number to each rule. Rules using the vertical
  622. bar notation are distinct rules. The number assigned to the rule
  623. appears in the description file.
  624. .P
  625. The elements comprising a BODY are:
  626. .IP "\fIname\fR,\ \fIliteral\fR" 10
  627. These form the rules of the grammar:
  628. .IR name
  629. is either a
  630. .IR token
  631. or a
  632. .IR non-terminal ;
  633. .IR literal
  634. stands for itself (less the lexically required quotation marks).
  635. .IP "\fIsemantic action\fR" 10
  636. .br
  637. With each grammar rule, the user can associate actions to be performed
  638. each time the rule is recognized in the input process. (Note that the
  639. word ``action'' can also refer to the actions of the parser\(emshift,
  640. reduce, and so on.)
  641. .RS 10
  642. .P
  643. These actions can return values and can obtain the values returned by
  644. previous actions. These values are kept in objects of type YYSTYPE
  645. (see
  646. .BR %union ).
  647. The result value of the action shall be kept on the parse stack with
  648. the left-hand side of the rule, to be accessed by other reductions as
  649. part of their right-hand side. By using the <\fItag\fP> information
  650. provided in the declarations section, the code generated by
  651. .IR yacc
  652. can be strictly type checked and contain arbitrary information. In
  653. addition, the lexical analyzer can provide the same kinds of values for
  654. tokens, if desired.
  655. .P
  656. An action is an arbitrary C statement and as such can do input or
  657. output, call subprograms, and alter external variables. An action is
  658. one or more C statements enclosed in curly braces
  659. .BR '{'
  660. and
  661. .BR '}' .
  662. The statements shall not contain unbalanced curly brace preprocessing
  663. tokens.
  664. .P
  665. Certain pseudo-variables can be used in the action. These are macros
  666. for access to data structures known internally to
  667. .IR yacc .
  668. .IP $$ 10
  669. The value of the action can be set by assigning it to $$. If type
  670. checking is enabled and the type of the value to be assigned cannot be
  671. determined, a diagnostic message may be generated.
  672. .IP "$\fInumber\fR" 10
  673. This refers to the value returned by the component specified by the
  674. token
  675. .IR number
  676. in the right side of a rule, reading from left to right;
  677. .IR number
  678. can be zero or negative. If
  679. .IR number
  680. is zero or negative, it refers to the data associated with the name on
  681. the parser's stack preceding the leftmost symbol of the current rule.
  682. (That is,
  683. .BR \(dq$0\(dq
  684. refers to the name immediately preceding the leftmost name in the
  685. current rule to be found on the parser's stack and
  686. .BR \(dq$-1\(dq
  687. refers to the symbol to
  688. .IR its
  689. left.) If
  690. .IR number
  691. refers to an element past the current point in the rule, or beyond the
  692. bottom of the stack, the result is undefined. If type checking is
  693. enabled and the type of the value to be assigned cannot be determined,
  694. a diagnostic message may be generated.
  695. .IP "$<\fItag\fR>\fInumber\fR" 10
  696. .br
  697. These correspond exactly to the corresponding symbols without the
  698. .IR tag
  699. inclusion, but allow for strict type checking (and preclude unwanted
  700. type conversions). The effect is that the macro is expanded to use
  701. .IR tag
  702. to select an element from the YYSTYPE union (using
  703. .IR dataname.tag ).
  704. This is particularly useful if
  705. .IR number
  706. is not positive.
  707. .IP "$<\fItag\fR>$" 10
  708. This imposes on the reference the type of the union member referenced
  709. by
  710. .IR tag .
  711. This construction is applicable when a reference to a left context
  712. value occurs in the grammar, and provides
  713. .IR yacc
  714. with a means for selecting a type.
  715. .P
  716. Actions can occur anywhere in a rule (not just at the end); an
  717. action can access values returned by actions to its left, and in turn
  718. the value it returns can be accessed by actions to its right. An
  719. action appearing in the middle of a rule shall be equivalent to
  720. replacing the action with a new non-terminal symbol and adding an empty
  721. rule with that non-terminal symbol on the left-hand side. The semantic
  722. action associated with the new rule shall be equivalent to the original
  723. action. The use of actions within rules might introduce conflicts that
  724. would not otherwise exist.
  725. .P
  726. By default, the value of a rule shall be the value of the first element
  727. in it. If the first element does not have a type (particularly in the
  728. case of a literal) and type checking is turned on by
  729. .BR %type ,
  730. an error message shall result.
  731. .RE
  732. .IP "\fIprecedence\fR" 10
  733. The keyword
  734. .BR %prec
  735. can be used to change the precedence level associated with a particular
  736. grammar rule. Examples of this are in cases where a unary and binary
  737. operator have the same symbolic representation, but need to be given
  738. different precedences, or where the handling of an ambiguous if-else
  739. construction is necessary. The reserved symbol
  740. .BR %prec
  741. can appear immediately after the body of the grammar rule and can be
  742. followed by a token name or a literal. It shall cause the precedence
  743. of the grammar rule to become that of the following token name or
  744. literal. The action for the rule as a whole can follow
  745. .BR %prec .
  746. .P
  747. If a program section follows, the application shall ensure that the
  748. grammar rules are terminated by
  749. .BR %% .
  750. .SS "Programs Section"
  751. .P
  752. The
  753. .IR programs
  754. section can include the definition of the lexical analyzer
  755. \fIyylex\fR(),
  756. and any other functions; for example, those used in the actions
  757. specified in the grammar rules. It is unspecified whether the programs
  758. section precedes or follows the semantic actions in the output file;
  759. therefore, if the application contains any macro definitions and
  760. declarations intended to apply to the code in the semantic actions, it
  761. shall place them within
  762. .BR \(dq%{\ ...\ %}\(dq
  763. in the declarations section.
  764. .SS "Input Grammar"
  765. .P
  766. The following input to
  767. .IR yacc
  768. yields a parser for the input to
  769. .IR yacc .
  770. This formal syntax takes precedence over the preceding text syntax
  771. description.
  772. .P
  773. The lexical structure is defined less precisely;
  774. .IR "Lexical Structure of the Grammar"
  775. defines most terms. The correspondence between the previous terms and
  776. the tokens below is as follows.
  777. .IP "\fBIDENTIFIER\fR" 12
  778. This corresponds to the concept of
  779. .IR name ,
  780. given previously. It also includes literals as defined previously.
  781. .IP "\fBC_IDENTIFIER\fR" 12
  782. This is a name, and additionally it is known to be followed by a
  783. <colon>.
  784. A literal cannot yield this token.
  785. .IP "\fBNUMBER\fR" 12
  786. A string of digits (a non-negative decimal integer).
  787. .IP "\fBTYPE\fR,\ \fBLEFT\fR,\ \fBMARK\fR,\ \fBLCURL\fR,\ \fBRCURL\fR" 12
  788. .br
  789. These correspond directly to
  790. .BR %type ,
  791. .BR %left ,
  792. .BR %% ,
  793. .BR %{ ,
  794. and
  795. .BR %} .
  796. .IP "\fB{\ .\|.\|.\ }\fR" 12
  797. This indicates C-language source code, with the possible inclusion of
  798. .BR '$'
  799. macros as discussed previously.
  800. .sp
  801. .RS 4
  802. .nf
  803. /* Grammar for the input to yacc. */
  804. /* Basic entries. */
  805. /* The following are recognized by the lexical analyzer. */
  806. .P
  807. %token IDENTIFIER /* Includes identifiers and literals */
  808. %token C_IDENTIFIER /* identifier (but not literal)
  809. followed by a :. */
  810. %token NUMBER /* [0-9][0-9]* */
  811. .P
  812. /* Reserved words : %type=>TYPE %left=>LEFT, and so on */
  813. .P
  814. %token LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION
  815. .P
  816. %token MARK /* The %% mark. */
  817. %token LCURL /* The %{ mark. */
  818. %token RCURL /* The %} mark. */
  819. .P
  820. /* 8-bit character literals stand for themselves; */
  821. /* tokens have to be defined for multi-byte characters. */
  822. .P
  823. %start spec
  824. .P
  825. %%
  826. .P
  827. spec : defs MARK rules tail
  828. ;
  829. tail : MARK
  830. {
  831. /* In this action, set up the rest of the file. */
  832. }
  833. | /* Empty; the second MARK is optional. */
  834. ;
  835. defs : /* Empty. */
  836. | defs def
  837. ;
  838. def : START IDENTIFIER
  839. | UNION
  840. {
  841. /* Copy union definition to output. */
  842. }
  843. | LCURL
  844. {
  845. /* Copy C code to output file. */
  846. }
  847. RCURL
  848. | rword tag nlist
  849. ;
  850. rword : TOKEN
  851. | LEFT
  852. | RIGHT
  853. | NONASSOC
  854. | TYPE
  855. ;
  856. tag : /* Empty: union tag ID optional. */
  857. | \(aq<\(aq IDENTIFIER \(aq>\(aq
  858. ;
  859. nlist : nmno
  860. | nlist nmno
  861. ;
  862. nmno : IDENTIFIER /* Note: literal invalid with % type. */
  863. | IDENTIFIER NUMBER /* Note: invalid with % type. */
  864. ;
  865. .P
  866. /* Rule section */
  867. .P
  868. rules : C_IDENTIFIER rbody prec
  869. | rules rule
  870. ;
  871. rule : C_IDENTIFIER rbody prec
  872. | \(aq|\(aq rbody prec
  873. ;
  874. rbody : /* empty */
  875. | rbody IDENTIFIER
  876. | rbody act
  877. ;
  878. act : \(aq{\(aq
  879. {
  880. /* Copy action, translate $$, and so on. */
  881. }
  882. \(aq}\(aq
  883. ;
  884. prec : /* Empty */
  885. | PREC IDENTIFIER
  886. | PREC IDENTIFIER act
  887. | prec \(aq;\(aq
  888. ;
  889. .fi
  890. .P
  891. .RE
  892. .sp
  893. .SS "Conflicts"
  894. .P
  895. The parser produced for an input grammar may contain states in which
  896. conflicts occur. The conflicts occur because the grammar is not
  897. LALR(1). An ambiguous grammar always contains at least one LALR(1)
  898. conflict. The
  899. .IR yacc
  900. utility shall resolve all conflicts, using either default rules or
  901. user-specified precedence rules.
  902. .P
  903. Conflicts are either shift/reduce conflicts or reduce/reduce
  904. conflicts. A shift/reduce conflict is where, for a given state and
  905. lookahead symbol, both a shift action and a reduce action are
  906. possible. A reduce/reduce conflict is where, for a given state and
  907. lookahead symbol, reductions by two different rules are possible.
  908. .P
  909. The rules below describe how to specify what actions to take when a
  910. conflict occurs. Not all shift/reduce conflicts can be successfully
  911. resolved this way because the conflict may be due to something other
  912. than ambiguity, so incautious use of these facilities can cause the
  913. language accepted by the parser to be much different from that which
  914. was intended. The description file shall contain sufficient
  915. information to understand the cause of the conflict. Where ambiguity
  916. is the reason either the default or explicit rules should be adequate
  917. to produce a working parser.
  918. .P
  919. The declared precedences and associativities (see
  920. .IR "Declarations Section")
  921. are used to resolve parsing conflicts as follows:
  922. .IP " 1." 4
  923. A precedence and associativity is associated with each grammar rule; it
  924. is the precedence and associativity of the last token or literal in the
  925. body of the rule. If the
  926. .BR %prec
  927. keyword is used, it overrides this default. Some grammar rules might
  928. not have both precedence and associativity.
  929. .IP " 2." 4
  930. If there is a shift/reduce conflict, and both the grammar rule and the
  931. input symbol have precedence and associativity associated with them,
  932. then the conflict is resolved in favor of the action (shift or reduce)
  933. associated with the higher precedence. If the precedences are the
  934. same, then the associativity is used; left associative implies reduce,
  935. right associative implies shift, and non-associative implies an error
  936. in the string being parsed.
  937. .IP " 3." 4
  938. When there is a shift/reduce conflict that cannot be resolved by rule
  939. 2, the shift is done. Conflicts resolved this way are counted in the
  940. diagnostic output described in
  941. .IR "Error Handling".
  942. .IP " 4." 4
  943. When there is a reduce/reduce conflict, a reduction is done by the
  944. grammar rule that occurs earlier in the input sequence. Conflicts
  945. resolved this way are counted in the diagnostic output described in
  946. .IR "Error Handling".
  947. .P
  948. Conflicts resolved by precedence or associativity shall not be counted
  949. in the shift/reduce and reduce/reduce conflicts reported by
  950. .IR yacc
  951. on either standard error or in the description file.
  952. .SS "Error Handling"
  953. .P
  954. The token
  955. .BR error
  956. shall be reserved for error handling. The name
  957. .BR error
  958. can be used in grammar rules. It indicates places where the parser can
  959. recover from a syntax error. The default value of
  960. .BR error
  961. shall be 256. Its value can be changed using a
  962. .BR %token
  963. declaration. The lexical analyzer should not return the value of
  964. .BR error .
  965. .P
  966. The parser shall detect a syntax error when it is in a state where the
  967. action associated with the lookahead symbol is
  968. .BR error .
  969. A semantic action can cause the parser to initiate error handling by
  970. executing the macro YYERROR. When YYERROR is executed, the semantic
  971. action passes control back to the parser. YYERROR cannot be used
  972. outside of semantic actions.
  973. .P
  974. When the parser detects a syntax error, it normally calls
  975. \fIyyerror\fR()
  976. with the character string
  977. .BR \(dqsyntax\ error\(dq
  978. as its argument. The call shall not be made if the parser is still
  979. recovering from a previous error when the error is detected. The
  980. parser is considered to be recovering from a previous error until the
  981. parser has shifted over at least three normal input symbols since the
  982. last error was detected or a semantic action has executed the macro
  983. .IR yyerrok .
  984. The parser shall not call
  985. \fIyyerror\fR()
  986. when YYERROR is executed.
  987. .P
  988. The macro function YYRECOVERING shall return 1 if a syntax error
  989. has been detected and the parser has not yet fully recovered from it.
  990. Otherwise, zero shall be returned.
  991. .P
  992. When a syntax error is detected by the parser, the parser shall check
  993. if a previous syntax error has been detected. If a previous error was
  994. detected, and if no normal input symbols have been shifted since the
  995. preceding error was detected, the parser checks if the lookahead symbol
  996. is an endmarker (see
  997. .IR "Interface to the Lexical Analyzer").
  998. If it is, the parser shall return with a non-zero value. Otherwise,
  999. the lookahead symbol shall be discarded and normal parsing shall
  1000. resume.
  1001. .P
  1002. When YYERROR is executed or when the parser detects a syntax error and
  1003. no previous error has been detected, or at least one normal input
  1004. symbol has been shifted since the previous error was detected, the
  1005. parser shall pop back one state at a time until the parse stack is
  1006. empty or the current state allows a shift over
  1007. .BR error .
  1008. If the parser empties the parse stack, it shall return with a non-zero
  1009. value. Otherwise, it shall shift over
  1010. .BR error
  1011. and then resume normal parsing. If the parser reads a lookahead symbol
  1012. before the error was detected, that symbol shall still be the lookahead
  1013. symbol when parsing is resumed.
  1014. .P
  1015. The macro
  1016. .IR yyerrok
  1017. in a semantic action shall cause the parser to act as if it has fully
  1018. recovered from any previous errors. The macro
  1019. .IR yyclearin
  1020. shall cause the parser to discard the current lookahead token. If the
  1021. current lookahead token has not yet been read,
  1022. .IR yyclearin
  1023. shall have no effect.
  1024. .P
  1025. The macro YYACCEPT shall cause the parser to return with the value
  1026. zero. The macro YYABORT shall cause the parser to return with a
  1027. non-zero value.
  1028. .SS "Interface to the Lexical Analyzer"
  1029. .P
  1030. The
  1031. \fIyylex\fR()
  1032. function is an integer-valued function that returns a
  1033. .IR "token number"
  1034. representing the kind of token read. If there is a value associated
  1035. with the token returned by
  1036. \fIyylex\fR()
  1037. (see the discussion of
  1038. .IR tag
  1039. above), it shall be assigned to the external variable
  1040. .IR yylval .
  1041. .P
  1042. If the parser and
  1043. \fIyylex\fR()
  1044. do not agree on these token numbers, reliable communication between
  1045. them cannot occur. For (single-byte character) literals, the token is
  1046. simply the numeric value of the character in the current character set.
  1047. The numbers for other tokens can either be chosen by
  1048. .IR yacc ,
  1049. or chosen by the user. In either case, the
  1050. .BR #define
  1051. construct of C is used to allow
  1052. \fIyylex\fR()
  1053. to return these numbers symbolically. The
  1054. .BR #define
  1055. statements are put into the code file, and the header file if that file
  1056. is requested. The set of characters permitted by
  1057. .IR yacc
  1058. in an identifier is larger than that permitted by C. Token names found
  1059. to contain such characters shall not be included in the
  1060. .BR #define
  1061. declarations.
  1062. .P
  1063. If the token numbers are chosen by
  1064. .IR yacc ,
  1065. the tokens other than literals shall be assigned numbers greater than
  1066. 256, although no order is implied. A token can be explicitly assigned a
  1067. number by following its first appearance in the declarations section
  1068. with a number. Names and literals not defined this way retain their
  1069. default definition. All token numbers assigned by
  1070. .IR yacc
  1071. shall be unique and distinct from the token numbers used for literals
  1072. and user-assigned tokens. If duplicate token numbers cause conflicts in
  1073. parser generation,
  1074. .IR yacc
  1075. shall report an error; otherwise, it is unspecified whether the token
  1076. assignment is accepted or an error is reported.
  1077. .P
  1078. The end of the input is marked by a special token called the
  1079. .IR endmarker ,
  1080. which has a token number that is zero or negative. (These values are
  1081. invalid for any other token.) All lexical analyzers shall return zero
  1082. or negative as a token number upon reaching the end of their input. If
  1083. the tokens up to, but excluding, the endmarker form a structure that
  1084. matches the start symbol, the parser shall accept the input. If the
  1085. endmarker is seen in any other context, it shall be considered an
  1086. error.
  1087. .SS "Completing the Program"
  1088. .P
  1089. In addition to
  1090. \fIyyparse\fR()
  1091. and
  1092. \fIyylex\fR(),
  1093. the functions
  1094. \fIyyerror\fR()
  1095. and
  1096. \fImain\fR()
  1097. are required to make a complete program. The application can supply
  1098. \fImain\fR()
  1099. and
  1100. \fIyyerror\fR(),
  1101. or those routines can be obtained from the
  1102. .IR yacc
  1103. library.
  1104. .SS "Yacc Library"
  1105. .P
  1106. The following functions shall appear only in the
  1107. .IR yacc
  1108. library accessible through the
  1109. .BR "\-l\ y"
  1110. operand to
  1111. .IR c99 ;
  1112. they can therefore be redefined by a conforming application:
  1113. .IP "\fBint\ \fImain\fR(\fBvoid\fR)" 6
  1114. .br
  1115. This function shall call
  1116. \fIyyparse\fR()
  1117. and exit with an unspecified value. Other actions within this function
  1118. are unspecified.
  1119. .IP "\fBint\ \fIyyerror\fR(\fBconst\ char\fR\ *\fIs\fR)" 6
  1120. .br
  1121. This function shall write the NUL-terminated argument to standard
  1122. error, followed by a
  1123. <newline>.
  1124. .P
  1125. The order of the
  1126. .BR "\-l\ y"
  1127. and
  1128. .BR "\-l\ l"
  1129. operands given to
  1130. .IR c99
  1131. is significant; the application shall either provide its own
  1132. \fImain\fR()
  1133. function or ensure that
  1134. .BR "\-l\ y"
  1135. precedes
  1136. .BR "\-l\ l" .
  1137. .SS "Debugging the Parser"
  1138. .P
  1139. The parser generated by
  1140. .IR yacc
  1141. shall have diagnostic facilities in it that can be optionally enabled
  1142. at either compile time or at runtime (if enabled at compile time).
  1143. The compilation of the runtime debugging code is under the control of
  1144. YYDEBUG, a preprocessor symbol. If YYDEBUG has a non-zero value, the
  1145. debugging code shall be included. If its value is zero, the code shall
  1146. not be included.
  1147. .P
  1148. In parsers where the debugging code has been included, the external
  1149. .BR int
  1150. .IR yydebug
  1151. can be used to turn debugging on (with a non-zero value) and off (zero
  1152. value) at runtime. The initial value of
  1153. .IR yydebug
  1154. shall be zero.
  1155. .P
  1156. When
  1157. .BR \-t
  1158. is specified, the code file shall be built such that, if YYDEBUG is not
  1159. already defined at compilation time (using the
  1160. .IR c99
  1161. .BR \-D
  1162. YYDEBUG option, for example), YYDEBUG shall be set explicitly to 1.
  1163. When
  1164. .BR \-t
  1165. is not specified, the code file shall be built such that, if YYDEBUG is
  1166. not already defined, it shall be set explicitly to zero.
  1167. .P
  1168. The format of the debugging output is unspecified but includes at least
  1169. enough information to determine the shift and reduce actions, and the
  1170. input symbols. It also provides information about error recovery.
  1171. .SS "Algorithms"
  1172. .P
  1173. The parser constructed by
  1174. .IR yacc
  1175. implements an LALR(1) parsing algorithm as documented in the
  1176. literature. It is unspecified whether the parser is table-driven or
  1177. direct-coded.
  1178. .P
  1179. A parser generated by
  1180. .IR yacc
  1181. shall never request an input symbol from
  1182. \fIyylex\fR()
  1183. while in a state where the only actions other than the error action are
  1184. reductions by a single rule.
  1185. .P
  1186. The literature of parsing theory defines these concepts.
  1187. .SS "Limits"
  1188. .P
  1189. The
  1190. .IR yacc
  1191. utility may have several internal tables. The minimum maximums for
  1192. these tables are shown in the following table. The exact meaning of
  1193. these values is implementation-defined. The implementation shall
  1194. define the relationship between these values and between them and any
  1195. error messages that the implementation may generate should it run out
  1196. of space for any internal structure. An implementation may combine
  1197. groups of these resources into a single pool as long as the total
  1198. available to the user does not fall below the sum of the sizes
  1199. specified by this section.
  1200. .br
  1201. .sp
  1202. .ce 1
  1203. \fBTable: Internal Limits in \fIyacc\fP\fR
  1204. .ad l
  1205. .TS
  1206. center box tab(@);
  1207. cB | cB | cB
  1208. cB | cB | cB
  1209. l | n | lw(3i).
  1210. @Minimum
  1211. Limit@Maximum@Description
  1212. _
  1213. {NTERMS}@126@Number of tokens.
  1214. {NNONTERM}@200@Number of non-terminals.
  1215. {NPROD}@300@Number of rules.
  1216. {NSTATES}@600@Number of states.
  1217. {MEMSIZE}@5\|200@T{
  1218. Length of rules. The total length, in names (tokens and
  1219. non-terminals), of all the rules of the grammar. The left-hand side is
  1220. counted for each rule, even if it is not explicitly repeated, as
  1221. specified in
  1222. .IR "Grammar Rules in yacc".
  1223. T}
  1224. {ACTSIZE}@4\|000@T{
  1225. Number of actions. ``Actions'' here (and in the description file)
  1226. refer to parser actions (shift, reduce, and so on) not to semantic
  1227. actions defined in
  1228. .IR "Grammar Rules in yacc".
  1229. T}
  1230. .TE
  1231. .ad b
  1232. .SH "EXIT STATUS"
  1233. The following exit values shall be returned:
  1234. .IP "\00" 6
  1235. Successful completion.
  1236. .IP >0 6
  1237. An error occurred.
  1238. .SH "CONSEQUENCES OF ERRORS"
  1239. If any errors are encountered, the run is aborted and
  1240. .IR yacc
  1241. exits with a non-zero status. Partial code files and header files
  1242. may be produced. The summary information in the description file
  1243. shall always be produced if the
  1244. .BR \-v
  1245. flag is present.
  1246. .LP
  1247. .IR "The following sections are informative."
  1248. .SH "APPLICATION USAGE"
  1249. Historical implementations experience name conflicts on the names
  1250. .BR yacc.tmp ,
  1251. .BR yacc.acts ,
  1252. .BR yacc.debug ,
  1253. .BR y.tab.c ,
  1254. .BR y.tab.h ,
  1255. and
  1256. .BR y.output
  1257. if more than one copy of
  1258. .IR yacc
  1259. is running in a single directory at one time. The
  1260. .BR \-b
  1261. option was added to overcome this problem. The related problem of
  1262. allowing multiple
  1263. .IR yacc
  1264. parsers to be placed in the same file was addressed by adding a
  1265. .BR \-p
  1266. option to override the previously hard-coded
  1267. .BR yy
  1268. variable prefix.
  1269. .P
  1270. The description of the
  1271. .BR \-p
  1272. option specifies the minimal set of function and variable names that
  1273. cause conflict when multiple parsers are linked together. YYSTYPE does
  1274. not need to be changed. Instead, the programmer can use
  1275. .BR \-b
  1276. to give the header files for different parsers different names, and
  1277. then the file with the
  1278. \fIyylex\fR()
  1279. for a given parser can include the header for that parser. Names such
  1280. as
  1281. .IR yyclearerr
  1282. do not need to be changed because they are used only in the actions;
  1283. they do not have linkage. It is possible that an implementation has
  1284. other names, either internal ones for implementing things such as
  1285. .IR yyclearerr ,
  1286. or providing non-standard features that it wants to change with
  1287. .BR \-p .
  1288. .P
  1289. Unary operators that are the same token as a binary operator in general
  1290. need their precedence adjusted. This is handled by the
  1291. .BR %prec
  1292. advisory symbol associated with the particular grammar rule defining
  1293. that unary operator. (See
  1294. .IR "Grammar Rules in yacc".)
  1295. Applications are not required to use this operator for unary operators,
  1296. but the grammars that do not require it are rare.
  1297. .SH EXAMPLES
  1298. Access to the
  1299. .IR yacc
  1300. library is obtained with library search operands to
  1301. .IR c99 .
  1302. To use the
  1303. .IR yacc
  1304. library
  1305. \fImain\fR():
  1306. .sp
  1307. .RS 4
  1308. .nf
  1309. c99 y.tab.c -l y
  1310. .fi
  1311. .P
  1312. .RE
  1313. .P
  1314. Both the
  1315. .IR lex
  1316. library and the
  1317. .IR yacc
  1318. library contain
  1319. \fImain\fR().
  1320. To access the
  1321. .IR yacc
  1322. \fImain\fR():
  1323. .sp
  1324. .RS 4
  1325. .nf
  1326. c99 y.tab.c lex.yy.c -l y -l l
  1327. .fi
  1328. .P
  1329. .RE
  1330. .P
  1331. This ensures that the
  1332. .IR yacc
  1333. library is searched first, so that its
  1334. \fImain\fR()
  1335. is used.
  1336. .P
  1337. The historical
  1338. .IR yacc
  1339. libraries have contained two simple functions that are normally coded
  1340. by the application programmer. These functions are similar to the
  1341. following code:
  1342. .sp
  1343. .RS 4
  1344. .nf
  1345. #include <locale.h>
  1346. int main(void)
  1347. {
  1348. extern int yyparse();
  1349. .P
  1350. setlocale(LC_ALL, "");
  1351. .P
  1352. /* If the following parser is one created by lex, the
  1353. application must be careful to ensure that LC_CTYPE
  1354. and LC_COLLATE are set to the POSIX locale. */
  1355. (void) yyparse();
  1356. return (0);
  1357. }
  1358. .P
  1359. #include <stdio.h>
  1360. .P
  1361. int yyerror(const char *msg)
  1362. {
  1363. (void) fprintf(stderr, "%s\en", msg);
  1364. return (0);
  1365. }
  1366. .fi
  1367. .P
  1368. .RE
  1369. .SH RATIONALE
  1370. The references in
  1371. .BR "Referenced Documents"
  1372. may be helpful in constructing the parser generator. The referenced DeRemer and Pennello article (along
  1373. with the works it references) describes a technique to generate parsers
  1374. that conform to this volume of POSIX.1\(hy2017. Work in this area continues to be done, so
  1375. implementors should consult current literature before doing any new
  1376. implementations. The original Knuth article is the theoretical basis for this
  1377. kind of parser, but the tables it generates are impractically large for
  1378. reasonable grammars and should not be used. The ``equivalent to''
  1379. wording is intentional to assure that the best tables that are LALR(1)
  1380. can be generated.
  1381. .P
  1382. There has been confusion between the class of grammars, the algorithms
  1383. needed to generate parsers, and the algorithms needed to parse the
  1384. languages. They are all reasonably orthogonal. In particular, a parser
  1385. generator that accepts the full range of LR(1) grammars need not
  1386. generate a table any more complex than one that accepts SLR(1) (a
  1387. relatively weak class of LR grammars) for a grammar that happens to be
  1388. SLR(1). Such an implementation need not recognize the case, either;
  1389. table compression can yield the SLR(1) table (or one even smaller than
  1390. that) without recognizing that the grammar is SLR(1).
  1391. The speed of an LR(1) parser for any class is dependent more upon the
  1392. table representation and compression (or the code generation if a
  1393. direct parser is generated) than upon the class of grammar that the
  1394. table generator handles.
  1395. .P
  1396. The speed of the parser generator is somewhat dependent upon the class
  1397. of grammar it handles. However, the original Knuth article algorithms for
  1398. constructing LR parsers were judged by its author to be impractically
  1399. slow at that time. Although full LR is more complex than LALR(1), as
  1400. computer speeds and algorithms improve, the difference (in terms of
  1401. acceptable wall-clock execution time) is becoming less significant.
  1402. .P
  1403. Potential authors are cautioned that the referenced DeRemer and Pennello article previously cited
  1404. identifies a bug (an over-simplification of the computation of LALR(1)
  1405. lookahead sets) in some of the LALR(1) algorithm statements that
  1406. preceded it to publication. They should take the time to seek out that
  1407. paper, as well as current relevant work, particularly Aho's.
  1408. .P
  1409. The
  1410. .BR \-b
  1411. option was added to provide a portable method for permitting
  1412. .IR yacc
  1413. to work on multiple separate parsers in the same directory. If a
  1414. directory contains more than one
  1415. .IR yacc
  1416. grammar, and both grammars are constructed at the same time (by, for
  1417. example, a parallel
  1418. .IR make
  1419. program), conflict results. While the solution is not historical
  1420. practice, it corrects a known deficiency in historical implementations.
  1421. Corresponding changes were made to all sections that referenced the
  1422. filenames
  1423. .BR y.tab.c
  1424. (now ``the code file''),
  1425. .BR y.tab.h
  1426. (now ``the header file''), and
  1427. .BR y.output
  1428. (now ``the description file'').
  1429. .P
  1430. The grammar for
  1431. .IR yacc
  1432. input is based on System V documentation. The textual description shows
  1433. there that the
  1434. .BR ';'
  1435. is required at the end of the rule. The grammar and the implementation
  1436. do not require this. (The use of
  1437. .BR C_IDENTIFIER
  1438. causes a reduce to occur in the right place.)
  1439. .P
  1440. Also, in that implementation, the constructs such as
  1441. .BR %token
  1442. can be terminated by a
  1443. <semicolon>,
  1444. but this is not permitted by the grammar. The keywords such as
  1445. .BR %token
  1446. can also appear in uppercase, which is again not discussed. In most
  1447. places where
  1448. .BR '%'
  1449. is used,
  1450. <backslash>
  1451. can be substituted, and there are alternate spellings for some of the
  1452. symbols (for example,
  1453. .BR %LEFT
  1454. can be
  1455. .BR \(dq%<\(dq
  1456. or even
  1457. .BR \(dq\e<\(dq ).
  1458. .P
  1459. Historically, <\fItag\fP> can contain any characters except
  1460. .BR '>' ,
  1461. including white space, in the implementation. However, since the
  1462. .IR tag
  1463. must reference an ISO\ C standard union member, in practice conforming
  1464. implementations need to support only the set of characters for ISO\ C standard
  1465. identifiers in this context.
  1466. .P
  1467. Some historical implementations are known to accept actions that are
  1468. terminated by a period. Historical implementations often allow
  1469. .BR '$'
  1470. in names. A conforming implementation does not need to support either
  1471. of these behaviors.
  1472. .P
  1473. Deciding when to use
  1474. .BR %prec
  1475. illustrates the difficulty in specifying the behavior of
  1476. .IR yacc .
  1477. There may be situations in which the
  1478. .IR grammar
  1479. is not, strictly speaking, in error, and yet
  1480. .IR yacc
  1481. cannot interpret it unambiguously. The resolution of ambiguities in the
  1482. grammar can in many instances be resolved by providing additional
  1483. information, such as using
  1484. .BR %type
  1485. or
  1486. .BR %union
  1487. declarations. It is often easier and it usually yields a smaller parser
  1488. to take this alternative when it is appropriate.
  1489. .P
  1490. The size and execution time of a program produced without the runtime
  1491. debugging code is usually smaller and slightly faster in historical
  1492. implementations.
  1493. .P
  1494. Statistics messages from several historical implementations include the
  1495. following types of information:
  1496. .sp
  1497. .RS 4
  1498. .nf
  1499. \fIn\fR/512 terminals, \fIn\fR/300 non-terminals
  1500. \fIn\fR/600 grammar rules, \fIn\fR/1\|500 states
  1501. \fIn\fR shift/reduce, \fIn\fR reduce/reduce conflicts reported
  1502. \fIn\fR/350 working sets used
  1503. Memory: states, etc. \fIn\fR/15\|000, parser \fIn\fR/15\|000
  1504. \fIn\fR/600 distinct lookahead sets
  1505. \fIn\fR extra closures
  1506. \fIn\fR shift entries, \fIn\fR exceptions
  1507. \fIn\fR goto entries
  1508. \fIn\fR entries saved by goto default
  1509. Optimizer space used: input \fIn\fR/15\|000, output \fIn\fR/15\|000
  1510. \fIn\fR table entries, \fIn\fR zero
  1511. Maximum spread: \fIn\fR, Maximum offset: \fIn\fR
  1512. .fi
  1513. .P
  1514. .RE
  1515. .P
  1516. The report of internal tables in the description file is left
  1517. implementation-defined because all aspects of these limits are also
  1518. implementation-defined. Some implementations may use dynamic
  1519. allocation techniques and have no specific limit values to report.
  1520. .P
  1521. The format of the
  1522. .BR y.output
  1523. file is not given because specification of the format was not seen to
  1524. enhance applications portability. The listing is primarily intended to
  1525. help human users understand and debug the parser; use of
  1526. .BR y.output
  1527. by a conforming application script would be unusual. Furthermore,
  1528. implementations have not produced consistent output and no popular
  1529. format was apparent. The format selected by the implementation should
  1530. be human-readable, in addition to the requirement that it be a text
  1531. file.
  1532. .P
  1533. Standard error reports are not specifically described because they are
  1534. seldom of use to conforming applications and there was no reason to
  1535. restrict implementations.
  1536. .P
  1537. Some implementations recognize
  1538. .BR \(dq={\(dq
  1539. as equivalent to
  1540. .BR '{'
  1541. because it appears in historical documentation. This construction was
  1542. recognized and documented as obsolete as long ago as 1978, in the
  1543. referenced \fIYacc: Yet Another Compiler-Compiler\fP. This volume of POSIX.1\(hy2017 chose to leave it as obsolete and omit it.
  1544. .P
  1545. Multi-byte characters should be recognized by the lexical analyzer and
  1546. returned as tokens. They should not be returned as multi-byte
  1547. character literals. The token
  1548. .BR error
  1549. that is used for error recovery is normally assigned the value 256 in
  1550. the historical implementation. Thus, the token value 256, which is used
  1551. in many multi-byte character sets, is not available for use as the
  1552. value of a user-defined token.
  1553. .SH "FUTURE DIRECTIONS"
  1554. None.
  1555. .SH "SEE ALSO"
  1556. .IR "\fIc99\fR\^",
  1557. .IR "\fIlex\fR\^"
  1558. .P
  1559. The Base Definitions volume of POSIX.1\(hy2017,
  1560. .IR "Chapter 8" ", " "Environment Variables",
  1561. .IR "Section 12.2" ", " "Utility Syntax Guidelines"
  1562. .\"
  1563. .SH COPYRIGHT
  1564. Portions of this text are reprinted and reproduced in electronic form
  1565. from IEEE Std 1003.1-2017, Standard for Information Technology
  1566. -- Portable Operating System Interface (POSIX), The Open Group Base
  1567. Specifications Issue 7, 2018 Edition,
  1568. Copyright (C) 2018 by the Institute of
  1569. Electrical and Electronics Engineers, Inc and The Open Group.
  1570. In the event of any discrepancy between this version and the original IEEE and
  1571. The Open Group Standard, the original IEEE and The Open Group Standard
  1572. is the referee document. The original Standard can be obtained online at
  1573. http://www.opengroup.org/unix/online.html .
  1574. .PP
  1575. Any typographical or formatting errors that appear
  1576. in this page are most likely
  1577. to have been introduced during the conversion of the source files to
  1578. man page format. To report such errors, see
  1579. https://www.kernel.org/doc/man-pages/reporting_bugs.html .