Lines Matching refs:grammar
131 * Grammar Layout:: Overall structure of a Bison grammar file.
159 * Gen: Rpcalc Gen. Running Bison on the grammar file.
182 * Grammar Outline:: Overall layout of the grammar file.
184 * Rules:: How to write grammar rules.
195 * Grammar Rules:: Syntax and usage of the grammar rules section.
202 * Actions:: An action is the semantic definition of a grammar rule.
335 annotated context-free grammar into an @acronym{LALR}(1) or
336 @acronym{GLR} parser for that grammar. Once you are proficient with
374 parser's implementation. (The actions from your grammar are inserted
415 * Grammar Layout:: Overall structure of a Bison grammar file.
421 @cindex context-free grammar
422 @cindex grammar, context-free
424 @dfn{context-free grammar}. This means that you specify one or more
437 order to specify the language Algol 60. Any grammar expressed in
438 @acronym{BNF} is a context-free grammar. The input to Bison is
443 There are various important subclasses of context-free grammar. Although it
449 @acronym{LR}(1) grammar, and @acronym{LALR}(1) involves additional
452 @acronym{LR}(1) grammar that fails to be @acronym{LALR}(1).
462 roughly that the next grammar rule to apply at any point in the input is
465 grammar can be @dfn{ambiguous}, meaning that there are multiple ways to
466 apply the grammar rules to get the same inputs. Even unambiguous
468 look-ahead always suffices to determine the next grammar rule to apply.
472 are able to handle any context-free grammar for which the number of
490 punctuation marks. So the terminal symbols of a grammar for C include
495 lexicography, not grammar.)
522 grammar of C by nonterminal symbols `expression', `statement',
523 `declaration' and `function definition'. The full grammar uses dozens of
531 @code{return} statement; this would be described with a grammar rule which
552 context-free grammar of C, this follows from the fact that `expression' is
556 tokens using the grammar rules. If the input is valid, the end result is
558 the grammar's start symbol. If we use a grammar for C, the entire input
564 @cindex Bison grammar
565 @cindex grammar, Bison
566 @cindex formal grammar
568 A formal grammar is a mathematical construct. To define the language
569 for Bison, you must write a file expressing the grammar in Bison syntax:
570 a @dfn{Bison grammar} file. @xref{Grammar File, ,Bison Grammar Files}.
572 A nonterminal symbol in the formal grammar is represented in Bison input
593 The grammar rules also have an expression in Bison syntax. For example,
612 A formal grammar selects tokens only by their classifications: for example,
621 3989 as constants in the program! Therefore, each token in a Bison grammar
626 The token type is a terminal symbol defined in the grammar, such as
629 group it with other tokens. The grammar rules know nothing about tokens
639 have the same token type @code{INTEGER} but value 3989. When a grammar
656 also produce some output based on the input. In a Bison grammar, a grammar
692 certain grammar rule at a given point. That is, it may not be able to
694 reductions (applications of a grammar rule) applies, or whether to apply
700 To use a grammar that is not easily modified to be @acronym{LALR}(1), a
725 outstanding actions either by precedences given to the grammar rules
800 grammar, where the parentheses are nested in the recursive rules for
842 Here is a Bison grammar corresponding to the example above. It
883 When used as a normal @acronym{LALR}(1) grammar, Bison correctly complains
904 No change in the grammar itself is required. Now the
940 Let's consider an example, vastly simplified from a C++ grammar.
986 This models a problematic part of the C++ grammar---the ambiguity between
1003 however, neither of these parses ``dies,'' because the grammar as it stands is
1010 grammar of how to choose between the competing parses.
1207 When you run Bison, you give it a Bison grammar file as input. The output
1208 is a C source file that parses the language described by the grammar.
1215 the grammar rules---for example, to build identifiers and operators into
1216 expressions. As it does this, it runs the actions for the grammar rules it
1228 @code{yyparse} which implements that grammar. This function does not make
1243 or @samp{YY} in the Bison grammar file except for the ones defined in
1263 The actual language-design process using Bison, from grammar specification
1268 Formally specify the grammar in a form recognized by Bison
1292 Run Bison on the grammar to produce the parser.
1303 @cindex grammar file
1305 @cindex format of grammar file
1306 @cindex layout of Bison grammar
1308 The input file for the Bison utility is a @dfn{Bison grammar file}. The
1309 general form of a Bison grammar file is as follows:
1326 in every Bison grammar file to separate the sections.
1333 used by the actions in the grammar rules.
1339 The grammar rules define how to construct each nonterminal symbol from its
1394 * Gen: Rpcalc Gen. Running Bison on the grammar file.
1451 Here are the grammar rules for the reverse polish notation calculator.
1648 defined at the beginning of the grammar; @pxref{Rpcalc Decls,
1738 and continue parsing if the grammar contains a suitable error rule
1847 %% /* The grammar follows. */
1889 The other important new feature is the @code{%prec} in the grammar
1920 may be included in the grammar rules. In the example below it has
1932 This addition to the grammar allows for simple error recovery in the
1992 %% /* The grammar follows. */
2007 language. Therefore, grammar rules for this example will be very close
2169 back all nonnumeric characters as tokens, so new grammar rules suffice for
2238 %% /* The grammar follows. */
2241 The above grammar introduces only two new features of the Bison language.
2251 type with each grammar symbol whose semantic value is used. These symbols
2266 Here are the grammar rules for the multi-function calculator.
2299 /* End of grammar. */
2309 grammar rules (except for the actions) or the Bison declarations, but it
2574 Bison takes as input a context-free grammar specification and produces a
2575 C-language function that recognizes correct instances of the grammar.
2577 The Bison grammar input file conventionally has a name ending in @samp{.y}.
2581 * Grammar Outline:: Overall layout of the grammar file.
2583 * Rules:: How to write grammar rules.
2594 A Bison grammar file has four main sections, shown here with the
2618 * Grammar Rules:: Syntax and usage of the grammar rules section.
2629 of functions and variables that are used in the actions in the grammar
2679 @cindex grammar rules section
2680 @cindex rules section for grammar
2682 The @dfn{grammar rules} section contains one or more Bison grammar
2685 There must always be at least one grammar rule, and the first
2686 @samp{%%} (which precedes the grammar rules) may never be omitted even
2706 from the grammar rules.
2711 of the grammar file.
2724 class of syntactically equivalent tokens. You use the symbol in grammar
2732 equivalent groupings. The symbol name is used in writing grammar rules.
2738 There are three ways of writing terminal symbols in the grammar:
2752 written in the grammar using the same syntax used in C for character
2811 Whichever way you write the token type in the grammar rules, you write
2828 If you want to write a grammar that is portable to any Standard C
2859 @cindex grammar rule syntax
2860 @cindex syntax of grammar rules
2862 A Bison grammar rule has the following general form:
3031 The grammar rules for a language determine only the syntax. The semantics
3043 * Actions:: An action is the semantic definition of a grammar rule.
3072 This macro definition must go in the prologue of the grammar file
3400 If the grammar is such that a declaration can be distinguished from a
3447 Though grammar rules and semantic actions are enough to write a fully
3641 The @dfn{Bison declarations} section of a Bison grammar defines the symbols
3642 used in formulating the grammar and the data types of semantic values.
3675 You may require the minimum version of Bison to process the grammar. If
3745 For example, a grammar for the C language might specify these names with
3756 interchangeably in further declarations or the grammar rules. The
3998 Bison normally warns if there are any conflicts in the grammar
4032 Compile your grammar without @code{%expect}. Use the @samp{-v} option
4038 resolution is what you really want. If not, rewrite the grammar and
4057 Bison assumes by default that the start symbol for the grammar is the first
4058 nonterminal specified in the grammar specification section. The programmer
4101 Whether the parser is pure has nothing to do with the grammar rules.
4103 valid grammar.
4111 Here is a summary of the declarations used to define a grammar:
4152 Specify the grammar's start symbol (@pxref{Start Decl, ,The
4175 names defined in the grammar as well as a few other declarations.
4217 the grammar uses the special @samp{@@@var{n}} tokens, but if your
4218 grammar does not use it, using @samp{%locations} allows for more
4248 This option also tells Bison to write the C code for the grammar actions
4257 your source file (the grammar file). This directive causes them to
4283 defined in the grammar file.
4304 The number of grammar rules,
4365 in the grammar file, you are likely to run into trouble.
4445 In the grammar actions, use expressions like this to refer to the data:
4463 grammar file. If @code{yylex} is defined in a separate source file, you
4488 When a token is referred to in the grammar rules by a name, that name
4493 When a token is referred to in the grammar rules by a character literal,
4522 If the grammar uses literal string tokens, there are two ways that
4527 If the grammar defines symbolic token names as aliases for the
4530 the grammar file has no effect on @code{yylex}.
4651 If the grammar file does not use the @samp{@@} constructs to refer to
4707 action in the grammar can also explicitly proclaim an error, using the
4749 error recovery if you have written suitable error recovery grammar rules
5076 grammar rule, they can be combined according to that rule. This is called
5108 to a single grouping whose symbol is the grammar's start-symbol
5239 The conflict exists because the grammar as written is ambiguous: either
5244 write an unambiguous grammar, but that is very hard to do in this case.)
5300 Consider the following ambiguous grammar fragment (ambiguous because the
5485 to resolve it, either by changing your grammar or by adding an
5487 grammar, but it helps to protect against incorrect rule precedences.
5526 in the grammar.
5565 appears first in the grammar, but it is very risky to rely on this. Every
5672 It would seem that this grammar can be parsed with only a single token
5675 @code{ID} follows. In other words, this grammar is @acronym{LR}(1).
5680 @acronym{LR}(1) grammars. In this grammar, two contexts, that after
5690 occurrence means that the grammar is not @acronym{LALR}(1).
5772 When you use the @samp{%glr-parser} declaration in your grammar file,
5797 grammar symbol that produces the same segment of the input token
5814 permits the processing of any @acronym{LALR}(1) grammar in linear time (in the
5816 @acronym{LALR}(1)) grammar in
5818 context-free grammar in cubic worst-case time. However, Bison currently
5824 Usually, nondeterminism in a grammar is local---the parser is ``in
5827 grammar, in particular, it is only slightly slower than with the default
5950 The choice of error rules in the grammar is a choice of strategies for
6051 The grammar rules can then express the context dependency by the choice of
6255 The following grammar file, @file{calc.y}, will be used in the sequel:
6331 The next section reproduces the exact grammar that Bison used:
6536 conflict means that either the grammar is ambiguous, or the parser lacks
6537 information to make the right decision. Indeed the grammar is
6640 If a Bison grammar compiles properly but doesn't do what you want when it
6651 YYDEBUG 1} in the prologue of the grammar file (@pxref{Prologue, , The
6708 grammar are to blame.
6714 the grammar it is working.
6759 Here @var{infile} is the grammar file name, which usually ends in
6765 C++ code instead of C in your grammar file, to name it @file{foo.ypp}
6843 traditional Yacc grammars. If your grammar uses a Bison extension
6877 grammar file. This option causes them to associate errors with the
6897 the grammar, as well as a few other declarations. @xref{Decl Summary}.
6914 Description of the grammar, conflicts (resolved and unresolved), and
6929 file containing verbose descriptions of the grammar and
6940 Output a @acronym{VCG} definition of the @acronym{LALR}(1) grammar
6941 automaton computed by Bison. If the grammar file is @file{foo.y}, the
7032 grammar preamble. When run, @command{bison} will create several
7249 Of course the grammar is dedicated to arithmetics, a single
7417 the grammar for.
7538 The grammar itself is straightforward.
7945 implementations. In fact, I could use a single grammar but with
8049 If the bug is parser-related, you should include the smallest grammar
8050 you can which demonstrates the bug. The grammar file should also be
8052 to edit or add anything). The smaller and simpler the grammar, the
8135 Delimiter used to separate the grammar rule section from the
8169 Start-Symbol}. It cannot be used in the grammar.
8202 used in the grammar.
8207 grammar rules so as to allow the Bison parser to recognize an error in
8208 the grammar without halting the process. In effect, a sentence
8328 @code{yylex} are mapped. It cannot be used in the grammar, rather, use
8428 grammar actions.
8531 parsed, and the states correspond to various stages in the grammar
8579 A flag, set by actions in the grammar rules, which alters the way
8599 A grammar symbol standing for a grammatical construct that can
8614 nonterminal, according to a grammar rule. @xref{Algorithm, ,The Bison
8661 that describes a token in the grammar is a terminal symbol.
8666 A grammar symbol that has no rules in the grammar and therefore is