Questions about algorithms that decide whether a given string belongs to a fixed formal language.
0
votes
1answer
25 views
Weak Precedence Grammar and Parsing
I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation?
Any ...
1
vote
0answers
46 views
Negative lookahead in LR parsing algorithm
Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.):
Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ;
...
5
votes
3answers
48 views
For regular languages A and B, determine whether B might match early in (A B)
I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most ...
1
vote
1answer
82 views
Regular vs LALR(1): what is faster
Supposing we have two grammars which define the same languge: regular one and LALR(1) one.
Both regular and LALR(1) algorithms are O(n) where n is input length.
Regexps are usually preferred for ...
2
votes
1answer
122 views
What are handles in parsing?
I have read a few algorithms for $LR(k)$ parser, in which there is a frequent mention of selecting a handle from the grammar given.
For example, one document said - "the essence of LR parsing is ...
4
votes
2answers
108 views
Is this grammar really LL(1) while not being LR(1)?
$S \rightarrow S$, $L(G) = \{\}$
LL(1) analysis:
We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$.
$FIRST(S)$ doesn't contain ε, so the parse table looks like this:
...
3
votes
1answer
76 views
LL grammars and left-recursiviity
Why LL(k) and LL(∞) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with ...
2
votes
1answer
66 views
Example of a parsing/rewriting system?
I am studying formal languages and playing with writing my own parsers for them. I have a context free grammar parser already that works well. I am wondering if anyone can point me towards actually ...
3
votes
3answers
288 views
How is this grammar LL(1)?
This is a question from the Dragon Book. This is the grammar:
$S \to AaAb \mid BbBa $
$A \to \varepsilon$
$B \to \varepsilon$
The question asks how to show that it is LL(1) but not ...
2
votes
2answers
218 views
Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$
I am having difficulty with one of the exercises in the Dragon Book:
Exercise 2.4.1(c): Construct recursive-descent parsers, starting with
the following grammars:
$$S \rightarrow 0S1\ |\ ...
2
votes
1answer
532 views
Left-Factoring a grammar into LL(1)
I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are ...
3
votes
1answer
167 views
What is an IELR(1)-parser?
I try to teach myself the usage of bison. The manpage bison(1) says about bison:
Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser ...
2
votes
3answers
348 views
Is this language LL(1) parseable?
I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.
$$L=\{a^nb^m|n,m\in\mathbb N\land n\ge m\}$$
Is my hypothesis true or is ...
6
votes
1answer
116 views
Can abstract syntax trees be unparsed in subexponential time?
Abstract problem description
The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. ...
5
votes
0answers
74 views
When did $LR(k)$ acquire the meaning “left-to-right scan, rightmost derivation?”
According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ ...
2
votes
1answer
1k views
Left recursion and left factoring — which one goes first?
if I have a grammar having a production that contains both left recursion and left factoring like
$\qquad \displaystyle F \to FBa \mid cDS \mid c$
which one has priority, left recursion or left ...
9
votes
2answers
406 views
Are regular expressions $LR(k)$?
If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
4
votes
2answers
75 views
Computing follow sets conservatively for a PEG grammar
Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good ...
9
votes
2answers
341 views
Does the language of Regular Expressions need a push down automata to parse it?
I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
0
votes
1answer
161 views
Is this grammar ambiguous?
I have the grammar:
$\qquad \begin{align}
S &\to S = P \mid S \neq P \mid P \\
P &\to NUM
\end{align}$
This grammar suffers from left recursion. To eliminate left recursion, I got:
...
7
votes
1answer
264 views
reduce reduce and shift reduce error in LALR grammar
I have to write a grammar for Pascal, and there is just one thing that is causing problems.
Lets say we have operators (sorted by priority from low to high):
Postfix ...
3
votes
1answer
209 views
From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table?
There is this question I read somewhere but could not answer myself.
Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a ...
6
votes
3answers
412 views
Why is using a lexer/parser on binary data so wrong?
I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also ...
6
votes
3answers
473 views
Deriving the regular expression for C-style /**/ comments
I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web:
...
2
votes
3answers
152 views
Understanding $\text{handle}$ in parsing problem
Originally http://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there
The BNF is defined as followed:
...
8
votes
1answer
133 views
Parsing arbitrary context-free grammars, mostly short snippets
I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, ...
15
votes
1answer
138 views
Is there any nongeneral CFG parsing algorithm that recognises EPAL?
EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar:
$S \rightarrow a a$
$S \rightarrow b b$
$S \rightarrow a S ...
17
votes
1answer
2k views
Language theoretic comparison of LL and LR grammars
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
