1
$\begingroup$

I have a basic question, but I cannot find an answer anywhere on the Web. I have the following grammar rules:

  1. S -> if C ;
  2. C -> O < O
  3. O -> O + i
  4. O -> i

The part than I`m interested in is at rules 1,2 and 4.

I have calculated First(O) = {i, +} and Last(O) = {i}.

So, First(C) = {i,+,<} and Last(C) = {<, i}.

Also, if <* First(C) and Last(C) >* ;

I have build the precedence table and now I want to parse the input: if < ;

So when i parse it, I first have if on top of my stack. Then I look at <, if <* <, so I push < on top of the stack. So now I compare < to ;, ; has higher precedence according to the rules, so I must pop. The last part is trivial, and leads me to S, thus accepting the sentence.

BUT, as we can clearly see from the rules, this sentence should not be accepted (we only have 1 <, not enough to form C in order to reduce it).

I have noticed that this happens because there is a symmetrical rule (rule 2 in our case), which means that if <* {i, <} >* ;, so we cannot verify that there was indeed an < or only an i.

What is the solution to this problem? How do we handle these special cases where symmetrical rules`s precedence relations overlap? I`m sure there must be one, because this grammar is conceptually close to a programming language parsing problem itself.

Thank you for your time!

$\endgroup$
4
$\begingroup$

It's not the symmetry of rule 2 which is the problem (whatever you mean by symmetry). The problem is (more or less) inherent to the operator precedence algorithm.

O-P parsing was dropped from the Dragon book between the first and second editions, presumably because the authors no longer believed to be a useful parsing technique [Note 1]. So I'm quoting from the first edition, which I still have on my bookshelf for odd sentimental reasons [Note 2]. And what it says is: (p. 203)

As a general parsing technique, operator-precedence has a number of disadvantages… since the relationship between a grammar for the language being parsed and the operator-precedence parser itself is tenuous, one cannot always be sure the parser accepts exactly the desired language.

And that's the case. Operator-precedence grammars tend to accept a superset of the desired language, and you need to augment them with a number of checks to ensure that invalid sentences like the one you threw at your parser don't actually get recognized.

The classic O-P construction -- the one I think you are referring to with your use of $First$ and $Last$ -- has two problems, one inherent to O-P parsing and the other which can be (mostly) avoided. The first problem is that all non-terminals look the same to an operator-precedence grammar. That's the essence of the O-P parsing technique, so there's not much that can be done about it. The other problem is that $First$ (and $Last$) don't even distinguish between the presence and absence of a non-terminal. For this reason, $First(O)$ (not to be confused the the $LL$ algorithm's $FIRST_k$ function) includes $\fbox{+}$, and $First(C)$ includes $\fbox{<}$. In both cases, the terminal would not be in the $LL$ $FIRST$ set, because it does not appear exactly at the beginning of the right-hand side, but rather immediately following the non-terminal at the beginning.

Given that the $First$ function can't distinguish between terminals which follow non-terminals and terminals which just start a production, it is hardly surprising that the parser doesn't really care whether or not $\fbox{<}$ has an argument. Regardless of whether there is an expression before the $\fbox{<}$ or not, the grammar simply sees that $\fbox{if} \lessdot \fbox{<}$. And consequently, it doesn't complain when the two tokens are consecutive.

Now, in theory, the O-P parser uses precedence relations only to find a possible handle. Once it does so, the parser should find the grammar rule for which the handle is the right-hand side, if any, or throw an error. But I've rarely seen a description of O-P parsing which actually does that. Instead, the simplifying assumption is made that you can figure out which rule to reduce with by just looking at the last terminal on the stack, and that the input is correct [Note 3].

It's actually pretty easy to extend O-P to get around this problem. The basic idea is to divide the relations into two classes: those which apply to adjacent terminals, and those which apply to terminals separated by a single-non-terminal. (Since the grammar is an operator grammar, those are the only two possibilities.) I refer to these as 0- and 1-superscripted relations, where the number refers to the number of intervening non-terminals.

To compute these relations, we start by compute two groups of $First$ and $Last$ sets, using the same subscript notation. So $First^0(N)$ is the set of terminals which immediately start a right-hand side of $N$, and $First^1(N)$ is the set of terminals which immediately follow a non-terminal which immediately starts a right-hand side.These two sets are not necessarily disjoint, for example in the case of an operator like $\fbox{-}$ which can be either prefix or infix, but their union is the classic $First(N)$ set.

More precisely, using the standard convention that lower-case letters $a$, $b$, $c$… represent terminals, upper-case letters $A$, $B$, $C$… represent non-terminals while $P$, $Q$… represent productions, and greek letters $\alpha$, $\beta$, $\gamma$… represent possibly-empty sequences of grammar symbols, either terminals or non-terminals, we define:

$$First^0(N) = \{ a : N \Rightarrow^* a\beta \}$$ $$First^1(N) = \{ a : N \Rightarrow^* B a\beta \}$$ $$Last^0(N) = \{ a : N \Rightarrow^* \beta a\}$$ $$Last^1(N) = \{ a : N \Rightarrow^* a\beta aB\}$$ Correspondingly, we define two of each precedence relationship.

$$a \lessdot^0 b \iff \exists N,B : N \to \alpha a B \beta, b \in First^0(B)$$ $$a \lessdot^1 b \iff \exists N,B : N \to \alpha a B \beta, b \in First^1(B)$$ $$a \gtrdot^0 b \iff \exists N,A : N \to \alpha A b \beta, a \in Last^0(A)$$ $$a \gtrdot^1 b \iff \exists N,A : N \to \alpha A b \beta, a \in Last^1(A)$$ $$a \doteq^0 b \iff \exists N : N \to \alpha a b \beta$$ $$a \doteq^1 b \iff \exists N,X : N \to \alpha a X b \beta$$ For each production $N \to \alpha A x \beta$, add $Last_0(A) \gtrdot_0 x$ and $Last_1(A) \gtrdot_1 x$

To parse, we use essentially the standard algorithm taking account of the presence or absence of non-terminals. Conceptually, we store both terminals and non-terminals on the stack. (In practice, I would keep separate stacks and use a flag on the terminal to indicate whether it has a non-terminal on top of it or not -- there can only be one, because it is an operator grammar.) At each step, we compare the incoming terminal with the topmost terminal on the stack. If the actual top of the stack is a non-terminal, we use the 1-superscripted relations; otherwise, we use the 0-superscripted relations. As before, if no relation exists between the two terminals an error is signalled (and that will catch your error).

Now, to assist with the identification of the production corresponding to the handle, we can store a little bit more information on the stack. When we push a terminal onto the stack, it is either because there was a $\lessdot$ relation with the previous stacked terminal, in which case we are starting a right-hand side, or there was a $\doteq$ relation with the previous terminal, which must be part of the same right-hand side. In either case, we can record the prefix of the appropriate RHS (up to the curren point) instead of the terminal. That has two advantages.

  • it lets us distinguish between prefix and infix operators in a natural way; and

  • it really lets us assign them different precedences, because we can actually define the precedence relations as relations between RHS location and incoming terminal, instead of terminal and incoming terminal, thereby allowing a bit more discrimination. (That's needed to give unary minus tighter binding.)

Now before you rush out and start coding a parser generator based on this idea, please re-read [Note 1], because at this point we are 90% of the way to rediscovering $LR$ parsing. I really believe that if you follow this algorithm closely, you will gain some useful intuitions for understanding $LR$ parsing. And it should be obvious that it is only a small step between "extended" O-P parsing and a table-driven $LALR(1)$ parser, at which point you might as well haul out bison or some other yacc-derivative and let it build your parser for you. [Note 4]

Notes

  1. Personally, I would have dropped LL-parsing, but who am I to judge :) It's not that O-P parsing is at all useful once the LALR(1) construction algorithm is known. It isn't, and the problem you're having is a case in point. Any language parseable by O-P can be parsed correctly and unambiguously with LALR(1), and with the same computational complexity. (Indeed, with essentially the same amount of time and space.) The only reason to keep O-P hanging around at all is that (again, in my opinion), thinking about O-P parsing will (if you think about it the right way) lead you to the key insights which lead to LR parsing.

  2. I like the cover.

  3. In practice, there is another classic problem with O-P parsing, which was mentioned in the text I replaced with an … in the Dragon book quote: the algorithm as described can't distinguish between prefix and infix uses of $\fbox{-}$. The usual hack used to fix that problem is to use a small state machine (two states, typically) which is sufficient to reveal whether or not an operator was preceded by an operand. That's also sufficient to throw an error if an operator cannot be used as a prefix operator, so practical O-P parsers don't really have a problem. A while back, I described such an algorithm in a StackOverflow answer

  4. I'm sure I'm not the first person to have thought up this idea, in several decades of very clever people thinking about parsing algorithms, but I haven't ever seen it described anywhere. As I said, I worked it out while I was trying to grasp the mechanics of bottom-up parsing, and afterwards it seemed a bit redundant. But if anyone passing by happens to know a literature reference, I'd appreciate a pointer.

$\endgroup$
5
  • $\begingroup$ Awesome reply, thank you. I am a student, and so far, only the classic O-P construction has been presented to me, but indeed, the LALR(1) seems much more powerful at a first glance. Two more small questions though :D 1.When you defined the precedence relationships with the two First functions, the old rules still apply, right? i mean that alpha =* x in your example? or alpha and beta are just a string of terminals and non-terminals? and 2. On note 2, you said that you like the cover..what cover?:) $\endgroup$ – 7lym Jan 7 '17 at 11:07
  • $\begingroup$ We use the second edition of Dragon Book :). I understand now what you meant about the cover:)) I also understood the idea that you stated, just wanted to make sure, and I sketched something similar as a "bugfix" but wanted to double-check with others` opinion. Thanks again for this reply, you `ve been really helpful, I`ll mark this as the answer:) $\endgroup$ – 7lym Jan 7 '17 at 17:01
  • $\begingroup$ OK; I tried to be more precise both about notation and definitions, but I still haven't really described the final algorithm to my satisfaction. I might get back to it. Let me emphasize that what I've sketched here is not the version of operator-precedence parsing you'll find in any standard textbook (as far as I know), but it is in some sense a formalisation of the actual code you will find in the wild, which understands things like unary minus. The nonterminal-aware sets and relations are something I came up with myself, many years ago, as I was grappling with exactly your problem. $\endgroup$ – rici Jan 7 '17 at 18:03
  • $\begingroup$ @rici I am following you for compilers, your answers really help me. I have posted one question, I think you can answer this can you please check this once 'cs.stackexchange.com/questions/131108/…' $\endgroup$ – Prasanna Oct 12 '20 at 14:05
  • $\begingroup$ @PrasannaSasne: That question really doesn't belong on this site. It's a programming question. Move it to Stack Overflow and I'll try to respond. $\endgroup$ – rici Oct 12 '20 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.