Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
486 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
0
answers
36
views
Are there exceptions where a grammar is left-recursive or not left-factored but still LL(1)?
The Internet is full of claims that an $LL(1)$ grammar cannot be ambiguous, left-recursive, or not left-factored.
But is the statement "An $LL(1)$ grammar cannot be non-left-factored or left-...
0
votes
0
answers
56
views
How to minimize parentheses when stringifying arithmetic AST for right-to-left evaluation languages with different precedence rule?
I'm looking at translations to and from APL, which has right-to-left evaluation and no operator precedence. Is there a known algorithm to minimize parentheses usage when keeping the same operators for ...
1
vote
1
answer
130
views
How do we usually specify whitespace in BNF?
I'm looking at The Hyperlinked C++ BNF and it's not really specified or mentioned even though whitespace is obviously very important to parsing C or C++.
If we simply say whitespace is ignored between ...
0
votes
0
answers
33
views
Is my idea novel, for dynamically demoting the precedence of an infix operator during precedence parsing?
I have implemented a variant of the Shunting Yard algorithm which nicely handles prefix, infix and postfix operators, at arbitrary precedence levels.
In the parser, various monadic math functions are ...
0
votes
2
answers
105
views
Tell mid-process whether parsing is complete
This is relevant for languages that can be used both interactively and scripted (think Shell, or Python).
For these languages, they offer, in addition to a mode for running scripts, an interactive ...
2
votes
2
answers
135
views
Are there definitions of "deterministic" or "unambiguous" for EBNF-style grammars?
My understanding is that an EBNF-style grammar (similar to a Context-Free Grammar (CFG) but with added optionals, repetition and/or grouping) defines a language, but doesn't correspond to a particular ...
1
vote
1
answer
130
views
What is the difference between a DOM and a syntax tree?
In my understanding, given the same input that is an XML or an HTML document,
If you use a DOM parser you will get a DOM
If you use an HTML parser you will get a ...
0
votes
2
answers
82
views
Does a language recognizer require an unambiguous context-free grammar?
The reference manual for Lua contains a complete EBNF grammar for the language. However, it's simplified compared to the grammar used by the actual Lua parser.
In particular, the simplified grammar is ...
0
votes
1
answer
100
views
Number of LR(0) item sets of the grammar (Dragon Book, exercise 4.6.7)
I'm stuck on exercise 4.6.7 part b from the dragon book. The task is to show that the given grammar Gn:
S → Aibi for 1 ≤ i ≤ nAi → ajAi | aj for 1 ≤ i,j ≤ n i≠j
has ...
1
vote
1
answer
98
views
Possible mistake in a book regarding parsing and lexical analysis
I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage :
"From a practical point of view, for each grammar G = (Σ,V, S, P) ...
1
vote
0
answers
53
views
Effect of slight modification to LL(1) parse table generation
I am experimenting with LL(1) parsers that do not use a separate lexer.
I have the following grammar:
S = (('<' S '>' | 'a'+) ' '?)+
The notation uses ' ...
0
votes
1
answer
70
views
Discard all ambiguity from given CFG
Here is given CFG :
CODE→VDECL CODE | FDECL CODE | ε
VDECL→vtype id semi | vtype ASSIGN semicolon
ASSIGN→id assign RHS
RHS→EXPR | lit | char | bool
EXPR→EXPR addsub EXPR | EXPR multdiv EXPR
EXPR→...
2
votes
2
answers
104
views
Termination of standard encoding of CFG as PDA for words not in the language
The construction of a PDA from a CFG on wikipedia (1) is like a nice exercise for implementing a minimal-and-slow-but-functional parsing algorithm. I have a question about termination of the PDA that ...
0
votes
1
answer
89
views
Derivation for BNF
Given a grammar for something like: h(x) or function(x)
...
0
votes
2
answers
98
views
can left recursion be solved by adjusting the parser not the grammar?
Lets say I have a grammar
I know that E -> E + T | T can be solved like this: E -> T ( + T)*.
But instead can I just ...