Debian Codegraph @

documentation/manual/grammar/midrule.yo

raw
1 Occasionally it is useful to insert an action block somewhere in the middle of
2 a production rule. These so-called mid-rule action blocks are comparable to
3 the usual action blocks, appearing at the end of production rules, but
4 mid-rule action blocks are executed before the parser has recognized the
5 production rule's components that follow them.
6
7 A mid-rule action block can refer to the components preceding it using tt($i),
8 but it may not (cannot) refer to subsequent components because it is executed
9 before they have been observed.
10
11 The mid-rule action block itself counts as one of the components of the
12 production rule. In the example shown below, tt(stmnt) can be referred to as
13 tt($6) in the final action block.
14
15 Mid-rule action blocks can also have semantic values. When using tt(%union) or
16 tt(%polymorphic) and a rule's nonterminal is associated with a union field or
17 polymorphic token, then mid-rule action blocks loose those associations. When
18 the tt($$, $$.) or tt($$->) shorthand notations appear in mid-action blocks of
19 production rules whose nonterminal is associated with a polymorphic type or
20 union field then a warning is issued that automatic type associations do not
21 apply. Using the tt(_$$) shorthand notation prevents the warning from being
22 issued.
23
24 Here is an example from a hypothetical grammar, defining a tt(let) statement
25 that looks like `this:
26 verb(
27 let (variable) statement
28 )
29 Here, tt(variable) is the name of a variable that must only exists for the
30 tt(statement's) lifetime. To parse this construct, we must insert tt(variable)
31 into a symbol table before parsing tt(statement), and must remove it
32 afterward. Here is how it is done:
33 verb(
34 stmt:
35 LET '(' variable ')'
36 {
37 _$$.assign<SYMTAB>(symtab());
38 addVariable($3);
39 }
40 stmt
41 {
42 $$ = $6;
43 restoreSymtab($5);
44 }
45 )
46 As soon as `tt(let (variable))' has been recognized, the first action is
47 executed. It saves the current symbol table as the mid-rule's semantic value,
48 using the polymorphic tag tt(SYMTAB) (which could be associated with, e.g., an
49 tt(std::unordered_map)). Then tt(addVariable) receives the new variable's
50 name, adding it to the current symbol table. Once the first action is
51 finished, the embedded statement (tt(stmt)) is parsed. Note that the mid-rule
52 action is component number 5, so `tt(stmt)' is component number 6.
53
54 Once tt(statement) has been parsed, its semantic value is returned as the
55 semantic value of the production rule's nonterminal. Then the semantic value
56 from the mid-rule action block is used to restore the symbol table to its
57 original state. This removes the temporary tt(let)-variable from the list so
58 that it won't appear to exist while the rest of the program is parsed.
59
60 Defining mid-rule action blocks before a rule has completely been recognized
61 often leads to conflicts since the parser, because of the single look-ahead
62 tokoen, must make a decision about the parsing sequence to use. For example,
63 the following two rules, without mid-rule actions, can coexist because the
64 parser can always process the open-brace token and only then look at the next
65 token before deciding whether there is a declaration or not:
66 verb(
67 compound:
68 '{' declarations statements '}'
69 |
70 '{' statements '}'
71 ;
72 )
73 But when we an action block is inserted before the first open-parenthesis
74 a conflict is introduced:
75 verb(
76 compound:
77 {
78 prepareForLocalVariables();
79 }
80 '{' declarations statements '}'
81 |
82 '{' statements '}'
83 ;
84 )
85 Now the parser, encountering the open-parenthesis, must decide whether the
86 open-parenthesis belongs to the first or second production rule. It must make
87 this decision because it must execute the statement in the action block if it
88 selects the first production rule, while no action is required when selecting
89 the second production rule (cf. section ref(LOOKAHEAD)).
90
91 This problem cannot be solved by putting identical actions into the two rules,
92 like so:
93 verb(
94 {
95 prepareForLocalVariables();
96 }
97 '{' declarations statements '}'
98 |
99 {
100 prepareForLocalVariables();
101 }
102 '{' statements '}'
103 ;
104 )
105 But this does not solve the issue, because b() considers all action blocks
106 as unique elements of production rules, and does not inspect the action
107 blocks' contents.
108
109 A solution to the above problem consists of hiding the action block in a
110 support nonterminal symbol which recognizes the first block-open brace and
111 then performs the required preparations:
112 verb(
113 openblock:
114 '{'
115 {
116 prepareForLocalVariables();
117 }
118 ;
119
120 compound:
121 openblock declarations statements '}'
122 |
123 openblock statements '}'
124 ;
125 )
126 Now b() can execute the action in the rule for subroutine without
127 deciding which rule for compound it eventually uses. Note that the action
128 is now at the end of its rule. Any mid-rule action can be converted to an
129 end-of-rule action in this way, and this is what b() actually does to
130 implement mid-rule actions. B() converts mid-rule action blocks to hash-tag
131 numbered elements in production rules. In a rule like
132 verb(
133 string:
134 {
135 ...
136 }
137 TOKEN
138 ...
139 ;
140 )
141 warning messages referring to the mid-rule action block could look like
142 this:
143 verb(
144 [grammar: warning] Line 10: `rule 3: string -> #0001': ...
145 )
146 Here, `#0001' is the hidden nonterminal merely containing the mid-rule
147 action block. It is as though we had written this grammar:
148 verb(
149 string:
150 #0001 TOKEN
151 ...
152 ;
153
154 #0001:
155 {
156 ...
157 }
158 ;
159 )