![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ss4 CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps1 / 15.yacc|
Return to ss4 CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps1 / 15.yacc |
1.1 root 1: .\" @(#)ss4 6.1 (Berkeley) 5/8/86
2: .\"
3: .SH
4: 4: How the Parser Works
5: .PP
6: Yacc turns the specification file into a C program, which
7: parses the input according to the specification given.
8: The algorithm used to go from the
9: specification to the parser is complex, and will not be discussed
10: here (see
11: the references for more information).
12: The parser itself, however, is relatively simple,
13: and understanding how it works, while
14: not strictly necessary, will nevertheless make
15: treatment of error recovery and ambiguities much more
16: comprehensible.
17: .PP
18: The parser produced by Yacc consists
19: of a finite state machine with a stack.
20: The parser is also capable of reading and remembering the next
21: input token (called the
22: .I lookahead
23: token).
24: The
25: .I "current state"
26: is always the one on the top of the stack.
27: The states of the finite state machine are given
28: small integer labels; initially, the machine is in state 0,
29: the stack contains only state 0, and no lookahead token has been read.
30: .PP
31: The machine has only four actions available to it, called
32: .I shift ,
33: .I reduce ,
34: .I accept ,
35: and
36: .I error .
37: A move of the parser is done as follows:
38: .IP 1.
39: Based on its current state, the parser decides
40: whether it needs a lookahead token to decide
41: what action should be done; if it needs one, and does
42: not have one, it calls
43: .I yylex
44: to obtain the next token.
45: .IP 2.
46: Using the current state, and the lookahead token
47: if needed, the parser decides on its next action, and
48: carries it out.
49: This may result in states being pushed onto the stack, or popped off of
50: the stack, and in the lookahead token being processed
51: or left alone.
52: .PP
53: The
54: .I shift
55: action is the most common action the parser takes.
56: Whenever a shift action is taken, there is always
57: a lookahead token.
58: For example, in state 56 there may be
59: an action:
60: .DS
61: IF shift 34
62: .DE
63: which says, in state 56, if the lookahead token is IF,
64: the current state (56) is pushed down on the stack,
65: and state 34 becomes the current state (on the
66: top of the stack).
67: The lookahead token is cleared.
68: .PP
69: The
70: .I reduce
71: action keeps the stack from growing without
72: bounds.
73: Reduce actions are appropriate when the parser has seen
74: the right hand side of a grammar rule,
75: and is prepared to announce that it has seen
76: an instance of the rule, replacing the right hand side
77: by the left hand side.
78: It may be necessary to consult the lookahead token
79: to decide whether to reduce, but
80: usually it is not; in fact, the default
81: action (represented by a ``.'') is often a reduce action.
82: .PP
83: Reduce actions are associated with individual grammar rules.
84: Grammar rules are also given small integer
85: numbers, leading to some confusion.
86: The action
87: .DS
88: \fB.\fR reduce 18
89: .DE
90: refers to
91: .I "grammar rule"
92: 18, while the action
93: .DS
94: IF shift 34
95: .DE
96: refers to
97: .I state
98: 34.
99: .PP
100: Suppose the rule being reduced is
101: .DS
102: A \fB:\fR x y z ;
103: .DE
104: The reduce action depends on the
105: left hand symbol (A in this case), and the number of
106: symbols on the right hand side (three in this case).
107: To reduce, first pop off the top three states
108: from the stack
109: (In general, the number of states popped equals the number of symbols on the
110: right side of the rule).
111: In effect, these states were the ones
112: put on the stack while recognizing
113: .I x ,
114: .I y ,
115: and
116: .I z ,
117: and no longer serve any useful purpose.
118: After popping these states, a state is uncovered
119: which was the state the parser was in before beginning to
120: process the rule.
121: Using this uncovered state, and the symbol
122: on the left side of the rule, perform what is in
123: effect a shift of A.
124: A new state is obtained, pushed onto the stack, and parsing continues.
125: There are significant differences between the processing of
126: the left hand symbol and an ordinary shift of a token,
127: however, so this action is called a
128: .I goto
129: action.
130: In particular, the lookahead token is cleared by a shift, and
131: is not affected by a goto.
132: In any case, the uncovered state contains an entry such as:
133: .DS
134: A goto 20
135: .DE
136: causing state 20 to be pushed
137: onto the stack, and become the current state.
138: .PP
139: In effect, the reduce action ``turns back the clock'' in the parse,
140: popping the states off the stack to go back to the
141: state where the right hand side of the rule was first seen.
142: The parser then behaves as if it had seen the left side at that time.
143: If the right hand side of the rule is empty,
144: no states are popped off of the stack: the uncovered state
145: is in fact the current state.
146: .PP
147: The reduce action is also important in the treatment of user-supplied
148: actions and values.
149: When a rule is reduced, the code supplied with the rule is executed
150: before the stack is adjusted.
151: In addition to the stack holding the states, another stack,
152: running in parallel with it, holds the values returned
153: from the lexical analyzer and the actions.
154: When a shift takes place, the external variable
155: .I yylval
156: is copied onto the value stack.
157: After the return from the user code, the reduction is carried out.
158: When the
159: .I goto
160: action is done, the external variable
161: .I yyval
162: is copied onto the value stack.
163: The pseudo-variables $1, $2, etc., refer to the value stack.
164: .PP
165: The other two parser actions are conceptually much simpler.
166: The
167: .I accept
168: action indicates that the entire input has been seen and
169: that it matches the specification.
170: This action appears only when the lookahead token is
171: the endmarker, and indicates that the parser has successfully
172: done its job.
173: The
174: .I error
175: action, on the other hand, represents a place where the parser
176: can no longer continue parsing according to the specification.
177: The input tokens it has seen, together with the lookahead token,
178: cannot be followed by anything that would result
179: in a legal input.
180: The parser reports an error, and attempts to recover the situation and
181: resume parsing: the error recovery (as opposed to the detection of error)
182: will be covered in Section 7.
183: .PP
184: It is time for an example!
185: Consider the specification
186: .DS
187: %token DING DONG DELL
188: %%
189: rhyme : sound place
190: ;
191: sound : DING DONG
192: ;
193: place : DELL
194: ;
195: .DE
196: .PP
197: When Yacc is invoked with the
198: .B \-v
199: option, a file called
200: .I y.output
201: is produced, with a human-readable description of the parser.
202: The
203: .I y.output
204: file corresponding to the above grammar (with some statistics
205: stripped off the end) is:
206: .DS
207: state 0
208: $accept : \_rhyme $end
209:
210: DING shift 3
211: . error
212:
213: rhyme goto 1
214: sound goto 2
215:
216: state 1
217: $accept : rhyme\_$end
218:
219: $end accept
220: . error
221:
222: state 2
223: rhyme : sound\_place
224:
225: DELL shift 5
226: . error
227:
228: place goto 4
229:
230: state 3
231: sound : DING\_DONG
232:
233: DONG shift 6
234: . error
235:
236: state 4
237: rhyme : sound place\_ (1)
238:
239: . reduce 1
240:
241: state 5
242: place : DELL\_ (3)
243:
244: . reduce 3
245:
246: state 6
247: sound : DING DONG\_ (2)
248:
249: . reduce 2
250: .DE
251: Notice that, in addition to the actions for each state, there is a
252: description of the parsing rules being processed in each
253: state. The \_ character is used to indicate
254: what has been seen, and what is yet to come, in each rule.
255: Suppose the input is
256: .DS
257: DING DONG DELL
258: .DE
259: It is instructive to follow the steps of the parser while
260: processing this input.
261: .PP
262: Initially, the current state is state 0.
263: The parser needs to refer to the input in order to decide
264: between the actions available in state 0, so
265: the first token,
266: .I DING ,
267: is read, becoming the lookahead token.
268: The action in state 0 on
269: .I DING
270: is
271: is ``shift 3'', so state 3 is pushed onto the stack,
272: and the lookahead token is cleared.
273: State 3 becomes the current state.
274: The next token,
275: .I DONG ,
276: is read, becoming the lookahead token.
277: The action in state 3 on the token
278: .I DONG
279: is ``shift 6'',
280: so state 6 is pushed onto the stack, and the lookahead is cleared.
281: The stack now contains 0, 3, and 6.
282: In state 6, without even consulting the lookahead,
283: the parser reduces by rule 2.
284: .DS
285: sound : DING DONG
286: .DE
287: This rule has two symbols on the right hand side, so
288: two states, 6 and 3, are popped off of the stack, uncovering state 0.
289: Consulting the description of state 0, looking for a goto on
290: .I sound ,
291: .DS
292: sound goto 2
293: .DE
294: is obtained; thus state 2 is pushed onto the stack,
295: becoming the current state.
296: .PP
297: In state 2, the next token,
298: .I DELL ,
299: must be read.
300: The action is ``shift 5'', so state 5 is pushed onto the stack, which now has
301: 0, 2, and 5 on it, and the lookahead token is cleared.
302: In state 5, the only action is to reduce by rule 3.
303: This has one symbol on the right hand side, so one state, 5,
304: is popped off, and state 2 is uncovered.
305: The goto in state 2 on
306: .I place ,
307: the left side of rule 3,
308: is state 4.
309: Now, the stack contains 0, 2, and 4.
310: In state 4, the only action is to reduce by rule 1.
311: There are two symbols on the right, so the top two states are popped off,
312: uncovering state 0 again.
313: In state 0, there is a goto on
314: .I rhyme
315: causing the parser to enter state 1.
316: In state 1, the input is read; the endmarker is obtained,
317: indicated by ``$end'' in the
318: .I y.output
319: file.
320: The action in state 1 when the endmarker is seen is to accept,
321: successfully ending the parse.
322: .PP
323: The reader is urged to consider how the parser works
324: when confronted with such incorrect strings as
325: .I "DING DONG DONG" ,
326: .I "DING DONG" ,
327: .I "DING DONG DELL DELL" ,
328: etc.
329: A few minutes spend with this and other simple examples will
330: probably be repaid when problems arise in more complicated contexts.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.