![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ss6 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 ss6 CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps1 / 15.yacc |
1.1 root 1: .\" @(#)ss6 6.1 (Berkeley) 5/8/86
2: .\"
3: .SH
4: 6: Precedence
5: .PP
6: There is one common situation
7: where the rules given above for resolving conflicts are not sufficient;
8: this is in the parsing of arithmetic expressions.
9: Most of the commonly used constructions for arithmetic expressions can be naturally
10: described by the notion of
11: .I precedence
12: levels for operators, together with information about left
13: or right associativity.
14: It turns out that ambiguous grammars with appropriate disambiguating rules
15: can be used to create parsers that are faster and easier to
16: write than parsers constructed from unambiguous grammars.
17: The basic notion is to write grammar rules
18: of the form
19: .DS
20: expr : expr OP expr
21: .DE
22: and
23: .DS
24: expr : UNARY expr
25: .DE
26: for all binary and unary operators desired.
27: This creates a very ambiguous grammar, with many parsing conflicts.
28: As disambiguating rules, the user specifies the precedence, or binding
29: strength, of all the operators, and the associativity
30: of the binary operators.
31: This information is sufficient to allow Yacc to resolve the parsing conflicts
32: in accordance with these rules, and construct a parser that realizes the desired
33: precedences and associativities.
34: .PP
35: The precedences and associativities are attached to tokens in the declarations section.
36: This is done by a series of lines beginning with a Yacc keyword: %left, %right,
37: or %nonassoc, followed by a list of tokens.
38: All of the tokens on the same line are assumed to have the same precedence level
39: and associativity; the lines are listed in
40: order of increasing precedence or binding strength.
41: Thus,
42: .DS
43: %left \'+\' \'\-\'
44: %left \'*\' \'/\'
45: .DE
46: describes the precedence and associativity of the four arithmetic operators.
47: Plus and minus are left associative, and have lower precedence than
48: star and slash, which are also left associative.
49: The keyword %right is used to describe right associative operators,
50: and the keyword %nonassoc is used to describe operators, like
51: the operator .LT. in Fortran, that may not associate with themselves; thus,
52: .DS
53: A .LT. B .LT. C
54: .DE
55: is illegal in Fortran, and such an operator would be described with the keyword
56: %nonassoc in Yacc.
57: As an example of the behavior of these declarations, the description
58: .DS
59: %right \'=\'
60: %left \'+\' \'\-\'
61: %left \'*\' \'/\'
62:
63: %%
64:
65: expr : expr \'=\' expr
66: | expr \'+\' expr
67: | expr \'\-\' expr
68: | expr \'*\' expr
69: | expr \'/\' expr
70: | NAME
71: ;
72: .DE
73: might be used to structure the input
74: .DS
75: a = b = c*d \- e \- f*g
76: .DE
77: as follows:
78: .DS
79: a = ( b = ( ((c*d)\-e) \- (f*g) ) )
80: .DE
81: When this mechanism is used,
82: unary operators must, in general, be given a precedence.
83: Sometimes a unary operator and a binary operator
84: have the same symbolic representation, but different precedences.
85: An example is unary and binary \'\-\'; unary minus may be given the same
86: strength as multiplication, or even higher, while binary minus has a lower strength than
87: multiplication.
88: The keyword, %prec, changes the precedence level associated with a particular grammar rule.
89: %prec appears immediately after the body of the grammar rule, before the action or closing semicolon,
90: and is followed by a token name or literal.
91: It
92: causes the precedence of the grammar rule to become that of the following token name or literal.
93: For example, to make unary minus have the same precedence as multiplication the rules might resemble:
94: .DS
95: %left \'+\' \'\-\'
96: %left \'*\' \'/\'
97:
98: %%
99:
100: expr : expr \'+\' expr
101: | expr \'\-\' expr
102: | expr \'*\' expr
103: | expr \'/\' expr
104: | \'\-\' expr %prec \'*\'
105: | NAME
106: ;
107: .DE
108: .PP
109: A token declared
110: by %left, %right, and %nonassoc need not be, but may be, declared by %token as well.
111: .PP
112: The precedences and associativities are used by Yacc to
113: resolve parsing conflicts; they give rise to disambiguating rules.
114: Formally, the rules work as follows:
115: .IP 1.
116: The precedences and associativities are recorded for those tokens and literals
117: that have them.
118: .IP 2.
119: A precedence and associativity is associated with each grammar rule; it is the precedence
120: and associativity of the last token or literal in the body of the rule.
121: If the %prec construction is used, it overrides this default.
122: Some grammar rules may have no precedence and associativity associated with them.
123: .IP 3.
124: When there is a reduce/reduce conflict, or there is a shift/reduce conflict
125: and either the input symbol or the grammar rule has no precedence and associativity,
126: then the two disambiguating rules given at the beginning of the section are used,
127: and the conflicts are reported.
128: .IP 4.
129: If there is a shift/reduce conflict, and both the grammar rule and the input character
130: have precedence and associativity associated with them, then the conflict is resolved
131: in favor of the action (shift or reduce) associated with the higher precedence.
132: If the precedences are the same, then the associativity is used; left
133: associative implies reduce, right associative implies shift, and nonassociating
134: implies error.
135: .PP
136: Conflicts resolved by precedence are not counted in the number of shift/reduce and reduce/reduce
137: conflicts reported by Yacc.
138: This means that mistakes in the specification of precedences may
139: disguise errors in the input grammar; it is a good idea to be sparing
140: with precedences, and use them in an essentially ``cookbook'' fashion,
141: until some experience has been gained.
142: The
143: .I y.output
144: file
145: is very useful in deciding whether the parser is actually doing
146: what was intended.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.