Questions about algorithms that decide whether a given string belongs to a fixed formal language.

learn more… | top users | synonyms

0
votes
0answers
28 views

If a grammar is not LR(0) due to shift/reduce conflict, is it always LR(1)?

Also, is there any way to prove that a grammar is or isn't: 1) LR(0) 2) SLR(1) 3) LALR(1) 4) LR(1) without having to construct the parser table? Thank you!
0
votes
1answer
37 views

How does the Earley Parser store possible parses of an ambiguous sentence?

I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP) ), are both parses stored in one chart or in two? ...
2
votes
2answers
117 views

Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
4
votes
1answer
454 views

Is CYK still relevant today?

I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today. Is it or an extension of it still being used in compilers (for example), or have other ...
0
votes
0answers
18 views

Ambiguous grammar and parser LL(1) conflict

I am having some problems to solve this problem. I have to rewrite the following grammar to make it works with an LL(1) parser $$\begin{align*} S &\to  \text{noun} \mid \text{noun and noun} ...
0
votes
1answer
44 views

LR(0) expressive power

So I have grouped the following formalisms into a power hierarchy (and made classes for them): Class 1 DFA NFA NFAϵ reg.exp Class 2 (DCFL expressivity?) LR(1) DPDA Class 3 CFG PDA Class 4 ...
1
vote
0answers
14 views

What are the fundamental differences between predictive and LALR(1) parsers?

I'm reading the Dragon book. The beginning describes recursive descent parsers. Then it states that a predictive parser is the table version of a RD parser. I also read up on LALR(1) parsers. The ...
2
votes
2answers
76 views

BNF and Simultaneous Parsing

Let's say we have the following grammar expr1 ::= ... // Actual definition doesn't matter expr2 ::= ... // expr3 ;:= ... // foo ::= expr1 | expr2 | expr3 ...
0
votes
0answers
57 views

LALAR vs SLR Table for Given SLR Grammar

i'm so glad that ask my first question on my favorite site. Infact i ran into multiple choice question in recent exam on Compiler Course. Suppose T1, T2 is created with SLR(1) and LALR(1) for ...
0
votes
2answers
56 views

Are constituency grammars and dependency grammars two different types of context free grammars?

From http://en.wikipedia.org/wiki/Parse_tree A concrete syntax tree or parse tree or parsing tree[1] or derivation tree is an ordered, rooted tree that represents the syntactic structure of a ...
-5
votes
1answer
35 views

Show that this grammar is ambiguous [closed]

$E\rightarrow E+E | E*E | \neg E | (E) | num$ prove the above grammar is ambiguous by giving 2 different parse trees for the expression 4*(~3+5)
5
votes
1answer
85 views

How do I reconstruct the forest of syntax trees from the Earley vector?

Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
1
vote
0answers
72 views

LL(1) grammar for postfix ternary operations

Suppose the task is to make an LL(1) grammar for postfix operations, where the only operation is ternary. Obvious approach is $N$ - number $O$ - operation $S$ - expression ...
0
votes
1answer
50 views

LR(0) parsing: how can I know sets of items corresponding to states?

I'm studying LR(0) parser. But I don't understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following ...
0
votes
1answer
99 views

Computing FOLLOW sets for a LL(1) grammar

I am trying to learn compiler design. But I get confused when I have to deal with Follow set specifically for the empty word. I am trying to figure this out please help me with the same. ...
2
votes
1answer
67 views

parsing at semantic level due to ambiguities

I have a VHDL elaboration engine/simulator. As I understand it, the language syntax allows for ambiguities at syntax level. That is, an assignment ...
1
vote
2answers
61 views

What type of recursion is this?

I was trying to rule out whether this was LL(1) by checking for left-recursion in the following grammar: $\qquad A \to 0 A 1 \mid 0 1$ Which produces: $\qquad 0 A 1 \Rightarrow 0 0 A 1 1 ...
2
votes
1answer
38 views

Indentation based Grammars

Considering programming languages with significant whitespace for indentation, such as Python or Haskell. How does this whitespace fit into the grand schemes of programming language grammars. I can ...
1
vote
1answer
172 views

Is this grammar LR(1)

I am reading parser chapter from dragon book and I found a grammar over there - $ S \rightarrow L=R $ $ S \rightarrow R $ $L \rightarrow *R $ $L \rightarrow id $ $R \rightarrow L $ Now I have ...
2
votes
0answers
47 views

How does Earley parsing using an automaton work?

As described in this paper, you can use an pre-computed automaton to speed up an Earley parse. I'm not interested in the rigorous proof of this, but just how the basic algorithm works so that I can ...
0
votes
1answer
65 views

Parsing Dice Notation

The syntax of dice notation follows the following grammar: $$ Roll \rightarrow Dice | Dice'x'Int | More \quad Mod \quad More $$ $$ Dice \rightarrow Int_{1}'d'Int_2$$ $$ Mod \rightarrow '+'|'-'$$ $$ ...
1
vote
0answers
27 views

Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(a*a*)?(a*a*) and I convert it to a grammar: G ::= A B A ::= ...
1
vote
0answers
53 views

what does “Configuration is valid for a viable prefix ” actually means?

I am learning LR(1) parsing from the Dragon Book. I am really confused with this sentence. Formally we say that a configuration $[A \to u•v, a]$ is valid for a viable prefix $α$ if there is a ...
2
votes
4answers
623 views

What information do we get from a compiler's parse tree?

In the compiler course by Alex Aiken on Coursera, more specifically lecture 05-02 Context Free Grammars, the professor says that CFGs give answers of the type yes/no, i.e. whether the given string of ...
3
votes
3answers
208 views

How is non-ambuiguity different from determinism?

I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an ...
-1
votes
1answer
65 views

Representing grammar for list/dictionary with optional end separator as LL(1)

Considering a grammar that includes a dictionary or list with an optional terminal separator - e.g.: $$ \begin{align} obj \to & dict \\ &\mid OTHER \\ dict \to & ...
0
votes
1answer
60 views

Prove that the syntax is equivalent

I don't "see" why the following syntax is equivalent to the second syntax1: E -> E + T E -> T syntax2: ...
2
votes
1answer
50 views

Tokenizer and complex operators

I'm trying to create simple tokenizer to transform following (only part shown) search expression to tokens word1 near(1) word2 where word1, word2 are some words ...
2
votes
1answer
294 views

If a parser can parse a non-deterministic grammar, is the parser non-deterministic?

I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, S → 0S0 | 1S1 | ε, ...
0
votes
1answer
56 views

What is a preterm parser?

I am working with HOL-Light parser and keeping seeing references to preterm parser. What is a preterm parser? The most informative statement I find is from the HOL-Light reference for the ...
2
votes
1answer
187 views

How to prove formally that grammar isn't LR(1)

I want to prove that grammar $$ \begin{cases} S'\rightarrow S\\ S\rightarrow aSb ~|~ A\\ A\rightarrow bA~|~b \end{cases} $$ isn't $LR(1)$. I've constructed parser table and got Shift-Reduce conflict. ...
2
votes
2answers
78 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
76 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 ; ...
6
votes
3answers
79 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
143 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
960 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
219 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
111 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
131 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 ...
4
votes
3answers
3k 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
639 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\ |\ ...
4
votes
1answer
3k 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 ...
7
votes
1answer
478 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
756 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
156 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. ...
6
votes
0answers
123 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)$ ...
4
votes
1answer
5k 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 ...
10
votes
2answers
1k 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 ...
5
votes
2answers
93 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 ...
10
votes
2answers
652 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 ...