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 ...
- 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, ...
- 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-...
- 18.9k
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:
...
- 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/...
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 ...
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 ...
- 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.
- 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 ...
- 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 ...
- 136
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 ...
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 (...
- 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$ ...
- 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/...
- 171
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. ...
- 5,649
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 ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible