/docs/MyDocs

To get this branch, use:
bzr branch http://darksoft.org/webbzr/docs/MyDocs

« back to all changes in this revision

Viewing changes to Development/parsers/bison_grammar.txt

  • Committer: Suren A. Chilingaryan
  • Date: 2009-04-09 03:21:08 UTC
  • Revision ID: csa@dside.dyndns.org-20090409032108-w4edamdh4adrgdu3
import

Show diffs side-by-side

added added

removed removed

Lines of Context:
Development/parsers/bison_grammar.txt
 
1
Structure of bison grammar file
 
2
-------------------------------
 
3
%{
 
4
 - Extra statements to include in the begining of produced C file (normally
 
5
 includes and forward declarations).
 
6
 - defining the default data type of semantic values (int by default)
 
7
    #define YYSTYPE double
 
8
    + SHOULD be defined in lexer as well, otherwise will be considered int.
 
9
 - defining how deep the parser stack can grow before reporting an error
 
10
    #define YYMAXDEPTH ### (default 200)
 
11
%}
 
12
 
 
13
 list of tokens returned by lexical analyzer (see below)
 
14
 
 
15
%%
 
16
 
 
17
 definition of all nonterminal languages symbols (see below)
 
18
 
 
19
%%
 
20
 user code, should include following functions:
 
21
 1. function which is called in the case of error:
 
22
        void yyerror( const char *str) { }
 
23
 2. function main calling:
 
24
        yyparse();
 
25
 
 
26
-------------------------------------------------------------------------
 
27
 
 
28
List of Tokens
 
29
==============
 
30
 - we could/should define grouping order and  operator precedence
 
31
 
 
32
 %keyword <list of tokens>      - all listed tokens have same grouping priority
 
33
 %keyword <another list>        - this had higher grouping priority
 
34
 
 
35
 keywords - defining grouping order
 
36
 --------
 
37
 %left, %token  - left operators  ( x + y + z -> (x + y) + z )
 
38
 %right         - right operators ( x + y + z -> x + (y + z)
 
39
 %nonassoc      - no associativity ( x + y + z -> error )
 
40
 
 
41
 types - defining non-default token types
 
42
 -----
 
43
 %union {
 
44
    <type1> type1_name;
 
45
    <type2> type2_name;
 
46
 }
 
47
 %token <type2_name> TOKEN
 
48
 %token <tptr> VAR
 
49
 %type <type1_name> nonterminal /* defining types for non-terminal symbols */
 
50
 
 
51
 additional
 
52
 ----------
 
53
 %start <symbol>                /* specify start symbol - first non terminal 
 
54
                                by default */
 
55
 %pure_parser                   /* request producing of reentrant parser,
 
56
                                multiple calls from the same programm */
 
57
 %expect #                      /* eleminate shift/reduce conflicts warning */
 
58
 
 
59
 
 
60
Rules
 
61
=====
 
62
  - each nonterminal symbol must have grammatical rules showing how it is made 
 
63
  out of simpler constructs.
 
64
  - the start symbol should be defined
 
65
  - convention: TOKENS - upcase, nonterminals - lowcase (a terminal symbol that 
 
66
  stands for a particular keyword in the language should be named after that 
 
67
  keyword converted to upper case)
 
68
  - the single-symbol tokens could be returned from lexer just using ASCII code
 
69
  - the terminal symbol 'error' is reserved for error recovery. 
 
70
  
 
71
  - Examples:
 
72
  
 
73
 <symbol_name_1>:
 
74
    sequence of tokens and rules | another sequence | ... 
 
75
    { optional actions: Most of the time, the purpose of an action is to 
 
76
    compute the semantic value of the whole construct from the semantic values 
 
77
    of its parts. 
 
78
    - Default action: $$ = $1 (see below a meaning)
 
79
    }
 
80
    ;
 
81
 
 
82
 <symbol_name_2>:       - comma-separated sequence of 0 or more 's' groupings
 
83
    /* empty, to allow empty string matching */ | s
 
84
    ;
 
85
 
 
86
Rule
 
87
====
 
88
 - something like 'NUM op1 NUM'
 
89
 - Normally the precedence of rule (and, therefore precedence of whole 
 
90
 non-terminal symbol in the current semantical context) is equal to the
 
91
 precedence of last terminal symbol mentioned in it's components.
 
92
 However, using '%prec' keyword it is possible to directly specify symbol 
 
93
 which should identify the precedence of whole rule (this symbol is not
 
94
 mandatory to appear in the rule itself).
 
95
    exp:
 
96
        ....
 
97
        | exp '-' exp %prec BINARY_MINUS
 
98
        | '-' exp %prec UNARY_MINUS
 
99
 - For recovery there is special symbol 'error' which can be specified on
 
100
 rules line, it would be executed if everything else failed. Example:
 
101
    line:
 
102
        '\n'                    # empty line, ignoring
 
103
        | statement '\n' {}     # statement, processing
 
104
        | error '\n' {}         # error, executing recovery procedure
 
105
 
 
106
Actions
 
107
=======
 
108
 - Macroses to return imidiately from yyparse:
 
109
         YYACCEPT - return with success code
 
110
         YYABORT  - return with error code (1)
 
111
         YYERROR  - cause an immediate syntax error (does not return imideatly
 
112
                    but calls yyerror)
 
113
         
 
114
 - Macroses to calculate semantic values:
 
115
        $$      - semantic value of the resulting grouping should be written
 
116
                in this variable.
 
117
                 * $<type1_name>$       - for alternative types
 
118
        $n      - contains the semantic value for the nth component of the 
 
119
                current rule.
 
120
                 * $<type1_name>n       - for alternative types
 
121
 
 
122
        YYBACKUP (token, value) - Unshift token (installs a look-ahead token 
 
123
                with token type token and semantic value value, then it 
 
124
                discards value that was going to be reduced by this rule.
 
125
                Allowed only for rules that reduce a single value, and only 
 
126
                when there is no look-ahead token.
 
127
 
 
128
 - Look ahead macroses
 
129
        yychar          - current look ahead token (see algorithm)
 
130
 
 
131
 - Error recovery
 
132
    YYRECOVERING        - contains '1' when the parser recovering from a syntax
 
133
                        error and '0' - otherwise.
 
134
    yyclearin;          - discard current look-ahead token
 
135
    yyerrorok;          - resume generating error messages immediately for 
 
136
                        subsequent syntax errors.
 
137
 
 
138
    @n          - structure containing information on the line numbers and 
 
139
                column numbers of the 'n'th component of the current rule.
 
140
                    struct {
 
141
                        int first_line, last_line;
 
142
                        int first_column, last_column;
 
143
                    };
 
144
            + 'yylex' supply this information (for all or certain tokens)
 
145
            + use of this feature makes the parser noticeably slower.