Using rules from another parser?

[jason5122]

Hi, I have a parser that requires a subrule from a second parser I've made. The second parser deals with propositional logic (ϕ → ψ, ¬ϕ, etc.), and the parser using it contains one rule that uses the second parser's default rule (theorem), shown below:

I'm using embedded semantics in TypeScript (if that makes any difference), shown below:

public show = this.RULE('show', () => {
    this.CONSUME(Show);
    this.SUBRULE(this.separator);
    this.SUBRULE(this.theorem); // TODO: use LogicParser's rule
});

I tried something like this

const logicParser = new LogicParser();

// snip

public show = this.RULE('show', () => {
    this.CONSUME(Show);
    this.SUBRULE(this.separator);
    this.SUBRULE(logicParser.theorem);
});

but it fails to run after the self-analysis.

I know I can just duplicate the rules, but I was wondering if there is a better way to go about this. Thanks!

[jason5122]

It seems like the solution was simply to create an object of the logic parser and use that within the body of the subrule. It's probably better than importing rules anyways, which sounds messy even if it were possible.

[bd82]

It seems like the solution was simply to create an object of the logic parser and use that within the body of the subrule. It's probably better than importing rules anyways, which sounds messy even if it were possible.

That seems like a good solution in terms of separation of concerns.
But how do you handle subsets of the token vector?

[bd82]

There are a few patterns I am aware of in terms of structuring multiple parsers.

Inheritance

• inheritance
• inheritance2

Mixin like approach

• mixing in the different parts
• one of the component parts

I think the mixin like approach which are basically utility functions that are passed the parser's this ref and the token vocabulary.
could be used to share a single rule definition between two unrelated parser instances.

Generally Chevrotain is just plain JavaScript, So I am sure other ways to compose parsers will be possible...

[jason5122]

@bd82 By subsets of the token vectors, did you mean overlaps between them? Luckily for my use case, there is minimal overlap (whitespace being the only one) and all I needed to do was to parse the logical sentences and put them in a TS object for the subrule, so not much interaction there. Thanks for linking the inheritance examples, that's more what I was thinking of when I first wanted to share rules and I'll reference them if I ever run into anything deeper than my current issue.

On a sort of unrelated note, I am finishing up my two parsers but there is one slight issue:

<inference-rule>  ::= <statement> "dn" |
                      <statement> <statement> "mp" |
                      <statement> <statement> <statement> "sc"

<derivation-rule> ::= <statement> "dd" |
                      <statement> <statement> "id"

<statement>       ::= "placeholder" | <inference-rule>

This is a simplified BNF of the language (it has nothing to do with the inheritance issue). If I were to add rules for these as they are, I get an error about ambiguous lookaheads since inference-rule and derivation-rule start off roughly the same. I could refactor them so that they have the same start and I think that would work (?), but of course that breaks the recursive definition of inference-rule. Would you please help me structure the rules for this?

[bd82]

By subsets of the token vectors, did you mean overlaps between them?

Let me re-pharse:

• Do you have two parsers and two lexers?
• How do you divide the work? what part of the input text goes to the root parser and what part goes to the inner parser?
• What defines the text boundaries between the parsers?

Edit

I think I made a wrong assumption that the two parsers call each other...

[bd82]

This is a simplified BNF of the language (it has nothing to do with the inheritance issue). If I were to add rules for these as they are, I get an error about ambiguous lookaheads since inference-rule and derivation-rule start off roughly the same.

You have a couple of separate issues here:

Left Recursion

Your inference rule can invoke itself recursively which will cause an infinite loop in a recursive decent parser.
There is no workaround other than refactoring the grammar.

Common Prefix Ambiguity

Chevrotain is a lookahead parser, it need to be able to choose an alternative by looking at most K tokens ahead.
There are several workaround;

• extract the common part to a separate rule, and if needed perform some post parsing processing to farther distinguish the alternatives.
• use backtracking (not really recommended...)
• use complex custom optimized BACKTRACKING, e.g in the Java Parser implemented with chevrotain
  • example advanced backtracking rule
  • example advanced backtracking usage

Generally I would avoid BACKTRACKING if possible.
In the Java-Parser we implemented advanced optimized backtracking for the purpose of staying very strongly aligned with
the official specification style. The hope was that this will increase the correctness of the parser, However, this significantly reduces performance and will likely conflict with other features such as error recovery.