Return to ss6 CVS log

Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps1 / 15.yacc

Annotation of 43BSDReno/share/doc/ps1/15.yacc/ss6, revision 1.1

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.