Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
7 votes

Why Tomita created GLR and didn't use Earley?

Better late than never. If I understand correctly, Earley is top-down, and will spend time and memory creating Earley items for every production at a given S(i). This means that for natural language, ...
Jeff's user avatar
  • 171
7 votes

Difference between syntax and semantic error in programming languages

In the strictest sense, there is no real difference between syntax errors and semantics errors, at least as far as language theory is concerned: the only salient difference is the complexity of the ...
cody's user avatar
  • 13.9k
5 votes

Is classical lambda calculus grammar an `LL(k)` one?

After some trivial factorization, I think it should be easy to prove it's LL(1) by constructing the LL(1) table for it. The grammar would be: ...
nickie's user avatar
  • 283
4 votes

DPDA with parameterized states

Yes, there are lots of automata models for processing XML: I recommend you look into (extensions of) finite tree automata, see e.g. this text book as an intro
Patrick Totzke's user avatar
2 votes

Reducing the Height of Context-Free Grammars

The partial case is presented here: Balancing Straight-Line Programs for Strings and Trees. I'm not sure, that the problem can be solved in the general case.
gsv's user avatar
  • 421
2 votes

Generalizing Parsing Expression Grammar for Context Sensitive Grammars

PEGs are unambiguous exactly because at each choice point, i.e, alternatives of a grammar rule, you can choose one and never change it. Context-free grammars, or to be more precise general parsing ...
Wickoo's user avatar
  • 386
2 votes

Parse structure of a range concatenation grammar (RCG)

So, I'm actually going to reply to your edits first, then come back to your original question. re: Edit 1 In your first edit, you express some confusion over what a parse emitted by an Earley parser ...
eternaleye's user avatar
2 votes

Difference between syntax and semantic error in programming languages

It is hard to say. The boundary between "syntactic errors" and "static semantic errors" can be really blurred. One appropriate example would be Curry-style (extrinsic typing) and Church-style (...
xrq's user avatar
  • 1,175
2 votes

Recovering a parse forest from an Earley parser?

I'd like to echo the answers above by suggesting you read this paper: I would like to qualify though by saying that I have implemented the algorithm in ...
Jeremy Dohmann's user avatar
2 votes

Why can a Predictive Parser contain E' -> TE' | ε

... is not valid since we have "left recursion" (a variable that calls itself). That's not what a left recursion is. That's simply recursion. Direct left recursion is when a rule $A \to A\alpha$ ...
orlp's user avatar
  • 885
1 vote

Compressing grammars by introducing ambiguity and left-recursion

Regarding your second question about succinctness, there is a nonrecursive tradeoff in grammar size when moving from general cfgs to unambiguous cfgs. See here: Erik Meineche Schmidt, Thomas G. ...
Hermann Gruber's user avatar
1 vote

Permutation phrases with LR parsing

Have you considered converting this into a semantic problem? Instead of grammar rules for all permutations of nonterminals { A, B, C }, simply have one rule to recognize (A | B | C)^3 together with ...
PMar's user avatar
  • 11

Only top scored, non community-wiki answers of a minimum length are eligible