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.
I like the cover.
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 answerStackOverflow answer
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.
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.
I like the cover.
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
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.
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.
I like the cover.
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
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.
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)$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]
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]
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]
Now, in theory, the O-P parser isuses precedence relations only finding the possibleto find a possible handle. Once you've got a handleit does so, youthe parser should verify that itfind the grammar rule for which the handle is actually the right-hand side of some grammar rule, and issueif any, or throw an error message otherwise. 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].
Now, it'sIt's actually pretty easy to extend O-P to get around this problem. In essenceThe 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 definestart by compute two groups of $First$ functions (and two correspondingand $Last$ functions)sets, using the same subscript notation. So $First_0(N)$$First^0(N)$ is the set of terminals which immediately start a right-hand side of $N$, and $First_1(N)$$First^1(N)$ is the set of terminals which immediately follow a non-terminal which immediately starts a right-hand side. Both functions are recursive, as usual. (These two sets are not necessarily disjoint, for example in the case of an operator like $\fbox{-}$ which can be either prefix or infix.)
Correspondingly, we define two of each precedence relationshipbut their union is the classic $First(N)$ set.
For each productionMore precisely, using the standard convention that lower-case letters $N \to \alpha x A \beta$$a$, add $x \lessdot_0 First_0(A)$ and$b$, $x \lessdot_1 First_1(A)$
For each production$c$… represent terminals, upper-case letters $N \to \alpha A x \beta$$A$, add $Last_0(A) \gtrdot_0 x$$B$, $C$… represent non-terminals while $P$, $Q$… represent productions, and greek letters $Last_1(A) \gtrdot_1 x$$\alpha$, $\beta$, $\gamma$… represent possibly-empty sequences of grammar symbols, either terminals or non-terminals, we define:
For each production $N \to \alpha x y \beta$$$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, add $x \doteq_0 y$we define two of each precedence relationship.
For$$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 x A y \beta$$N \to \alpha A x \beta$, add $x \doteq_1 y$$Last_0(A) \gtrdot_0 x$ and $Last_1(A) \gtrdot_1 x$
To parse, we use essentially the samestandard algorithm, but taking account of the presence or notabsence 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-subscriptedsuperscripted relations; otherwise, we use the 0-subscriptedsuperscripted 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 location inprefix of the appropriate RHS along with the terminal. (In general, this might be a set of locations but for most common grammars there will just be one.) In fact, since the position in an RHS precisely defines the terminal, we can useup to the position instead ofcurren point) instead of the terminal. And thatThat has two secondary advantages:.
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.
I like the covercover.
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
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.
Now, in theory, the O-P parser is only finding the possible handle. Once you've got a handle, you should verify that it is actually the right-hand side of some grammar rule, and issue an error message otherwise. 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].
Now, it's actually pretty easy to extend O-P to get around this problem. In essence, we define two $First$ functions (and two corresponding $Last$ functions). $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. Both functions are recursive, as usual. (These two sets are not necessarily disjoint, for example in the case of an operator like $\fbox{-}$ which can be either prefix or infix.)
Correspondingly, we define two of each precedence relationship.
For each production $N \to \alpha x A \beta$, add $x \lessdot_0 First_0(A)$ and $x \lessdot_1 First_1(A)$
For each production $N \to \alpha A x \beta$, add $Last_0(A) \gtrdot_0 x$ and $Last_1(A) \gtrdot_1 x$
For each production $N \to \alpha x y \beta$, add $x \doteq_0 y$
For each production $N \to \alpha x A y \beta$, add $x \doteq_1 y$
To parse, we use essentially the same algorithm, but taking account of the presence or not 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-subscripted relations; otherwise, we use the 0-subscripted 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 location in the appropriate RHS along with the terminal. (In general, this might be a set of locations but for most common grammars there will just be one.) In fact, since the position in an RHS precisely defines the terminal, we can use the position instead of the terminal. And that has two secondary advantages:
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.
I like the cover.
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
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.
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.
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.
I like the cover.
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
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.