Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation?
Any help will be appreciated. If it is possible, could you give an example. Thanks
Weak precedence is first an algorithm for parsing (see Parsing Techniques - A Practical Guide 1st edition p. 186). So a weak precedence grammar would be a grammar which can be parsed by this algorithm (see the reference for a description of the algorithm, you'll probably want to start at least a few pages earlier).
IIRC, the interest of weak precedence parsing dropped at lot when practical LR(1) variants (SLR(1) and LALR(1)) were discovered, but precedence algorithms are still sometimes used in hand written parser for parsing expressions while the rest of the grammar is parsed with a recursive descend variant.
Weak precedence is a modification of Wirth-Weber "simple precedence" (which they introduced in a paper defining the language EULER). A simple precedence parser uses Boolean matrices to define three relations that can exist between any two symbols in the grammar, usually represented as <, =, and >. The algorithm reads the input, looking up the pairwise relations in tables generated from the Boolean matrices, and inserting the appropriate relation between each two symbols. When a > relation is discovered, the parser looks backward to the nearest < relation. The symbols between those constitute the right-hand side of a production in the grammar, which is then replaced by the nonterminal symbol on the left side of that production, and the parsing continues.
Problems occur when more than one relation can hold between two consecutive symbols. When this occurs, the grammar must be changed (usually by introducing new nonterminals) to keep the relationships clean, or the attempt to find a simple precedence grammar for the language must be abandoned. Jean Ichbiah and Steve Morse realized that this problem could be reduced by eliminating one of the relations, and they called the result "weak precedence." In a weak precedence parser, the only significant relation is >. Symbols in the input are processed until a > relation is found, then the series of symbols leading up to that is matched against the right-hand sides of all productions, with the longest possible match being taken. Reduction then occurs as in simple precedence, and parsing continues.
It is obvious that any simple precedence grammar is automatically also a weak precedence grammar. There are grammars, though, that are not simple precedence but are weak precedence grammars, so weak precedence is more powerful than simple precedence.
From memory I think it is in a paper by Ichbiah and Morse, CACM, 1970
