Skip to main content
added 607 characters in body
Source Link
Chris Dodd
  • 795
  • 2
  • 4

In traditional shift/reduce or bottom-up parsing, this is called a "reduce/reduce conflict" and needs to be resolved somehow. There are multiple approaches in roughly increasing order of complexity/difficulty:

  • using information from what you've seen already. This is what happens in a language like C using an LR parser -- you have a state machine that knows whether to expect an expression or an argument-expression-list (probably based on whether you're trying to parse an argument list or not)

  • using lookahead. Looking at future tokens to try to figure out which alternative to use.

  • using trial and backtracking -- try one, and if it doesn't work out, backtrack to this point and try the other.

  • using some kind of fork and join -- create multiple threads of processing where each alternative is explored in a separate thread, and then later prune threads that fail, and join non-failing threads back together in a common parent.

The main questions are how complex your grammar is, is it ambiguous, and what do you want to do about ambiguity? The first two alternatives above will generally fail for ambiguous grammars (but can be tweaked to chose one possible parse), the third will give you one possible parse, and the last will give all possible parses.

In traditional shift/reduce or bottom-up parsing, this is called a "reduce/reduce conflict" and needs to be resolved somehow

  • using information from what you've seen already. This is what happens in a language like C using an LR parser -- you have a state machine that knows whether to expect an expression or an argument-expression-list (probably based on whether you're trying to parse an argument list or not)

  • using lookahead. Looking at future tokens to try to figure out which alternative to use.

  • using trial and backtracking -- try one, and if it doesn't work out, backtrack to this point and try the other.

In traditional shift/reduce or bottom-up parsing, this is called a "reduce/reduce conflict" and needs to be resolved somehow. There are multiple approaches in roughly increasing order of complexity/difficulty:

  • using information from what you've seen already. This is what happens in a language like C using an LR parser -- you have a state machine that knows whether to expect an expression or an argument-expression-list (probably based on whether you're trying to parse an argument list or not)

  • using lookahead. Looking at future tokens to try to figure out which alternative to use.

  • using trial and backtracking -- try one, and if it doesn't work out, backtrack to this point and try the other.

  • using some kind of fork and join -- create multiple threads of processing where each alternative is explored in a separate thread, and then later prune threads that fail, and join non-failing threads back together in a common parent.

The main questions are how complex your grammar is, is it ambiguous, and what do you want to do about ambiguity? The first two alternatives above will generally fail for ambiguous grammars (but can be tweaked to chose one possible parse), the third will give you one possible parse, and the last will give all possible parses.

Source Link
Chris Dodd
  • 795
  • 2
  • 4

In traditional shift/reduce or bottom-up parsing, this is called a "reduce/reduce conflict" and needs to be resolved somehow

  • using information from what you've seen already. This is what happens in a language like C using an LR parser -- you have a state machine that knows whether to expect an expression or an argument-expression-list (probably based on whether you're trying to parse an argument list or not)

  • using lookahead. Looking at future tokens to try to figure out which alternative to use.

  • using trial and backtracking -- try one, and if it doesn't work out, backtrack to this point and try the other.