As of May 31, 2023, we have updated our Code of Conduct.

Hot answers tagged

7 votes
Accepted

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.6k
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
6 votes
Accepted

Fully linear time regular expression matching

Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-...
András Salamon's user avatar
5 votes
Accepted

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
  • 221
4 votes
Accepted

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 https://www.worldcat.org/title/...
Patrick Totzke's user avatar
4 votes

What is the grammar of network protocols and file formats?

There is an international agreed notation for describing protocols and format specifications (well actually there are several), which is ASN.1. It is a form of Context_free grammar notation. I used ...
Brian Tompsett - 汤莱恩's user avatar
4 votes
Accepted

Is $LL(k)$ for large $k$ considered harmful? If so, why?

The parsing table of a $LL(k)$ grammar grows exponentially in $k$. This is however the worst-case scenario, which is not typical, as Niel pointed out: For an $LL(k)$ grammar $G$, $k$ is the size of ...
Boson's user avatar
  • 560
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
  • 361
2 votes
Accepted

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
  • 376
2 votes
Accepted

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

Recovering a parse forest from an Earley parser?

I'd like to echo the answers above by suggesting you read this paper: http://dx.doi.org/10.1016/j.entcs.2008.03.044 I would like to qualify though by saying that I have implemented the algorithm in ...
Jeremy Dohmann'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,145
2 votes
Accepted

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
  • 690
2 votes

Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?

I ended up getting a hint on how to accomplish this by reading the leo semantics post from Jeffrey Kegler's deprecated Marpa algorithm page. https://metacpan.org/pod/release/JKEGL/Marpa-PP-0.005_006/...
Patrick Huber's user avatar
1 vote
Accepted

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