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

learn more… | top users | synonyms (1)

-1
votes
0answers
9 views

What are libraries for parsing grammars with Python? [closed]

I have had much fun playing with https://github.com/erikrose/parsimonious. It takes as input a simple grammar and parses a string into a tree. I know almost nothing about grammars and parsing, and I ...
2
votes
1answer
48 views

fixed point in regular expressions

I've posted this question first on StackOverflow but this section seems more suited for this kind of questions. Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll ...
1
vote
3answers
77 views

What techniques can I use to hand-write a parser for an ambiguous grammar?

I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a ...
7
votes
1answer
85 views

How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which ...
-1
votes
1answer
54 views

Why the given lexical specification will not process the following strings?

I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question. Here ...
3
votes
1answer
55 views

Removing left-recursion in grammar while maintaining left-association of operator

I have a problem with this exercise: Let G be the following ambiguous grammar for the λ-calculus: E → v | λv.E | EE | (E) where E is the single ...
0
votes
1answer
36 views

How do I form a parse tree for equations? [closed]

I have the following equation if (x > y) { if (y < a) { x:= a y:= b } else { x:= b; } } I was thinking of something like this ...
2
votes
1answer
32 views

Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?

Consider a grammar G which is SLR(1) except for some shift/reduce conflicts which can be resolved by imposing some precedence or associativity of operators. Is it the case that the construction of ...
2
votes
1answer
111 views

What is a real-world use-case/need for a left-recursive grammar?

I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as: ...like LL and LR parsing, PEGs are often frustrating to use in ...
1
vote
1answer
77 views

CFGs: detecting infinitely many derivations of a single string

Some particularly degenerate CFGs can produce a single string in infinitely many ways: for a dumb example, $S \to SS \mid \epsilon$ can produce the empty string as $S \to \epsilon$ or $S \to SS \to S ...
0
votes
0answers
57 views

LL(1) grammar for the untyped lambda-calculus

What I want to do I am trying to define a LL(1) grammar of the lambda-calculus. What I did Here is the grammar: $Term \to Abs$ $Term \to App$ $Abs \to \lambda \ id \ . \ Term$ $App \to Var \ ...
0
votes
0answers
35 views

from not LR(0) grammar to LR(0) grammar

Question from an exam: Given the grammar, $$\begin{align*} S&\to E\$\\ E&\to \mathrm{id} \mid \mathrm {id}(E) \end{align*}$$ Construct a grammar of the same language that ...
0
votes
1answer
42 views

How to create an LR($k$) grammar for a given language?

How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say: $$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = ...
9
votes
1answer
254 views

Why separate lexing and parsing?

It's possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test ...
0
votes
1answer
45 views

LL(k) Prediction Techniques (and Insight on method applied)

I'm requesting references for LL(k) in situations where k > 1 for reasons described below. I'm looking for ...
0
votes
2answers
62 views

generating recursive descent parser

I have a grammar, $L \to A \langle A \rangle^*$ $A \to () \mid (L)$ but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T ...
0
votes
1answer
37 views

Are regular grammars always LR(1)

The question is fairly straight forward. I just found a question on the internet that asks whether all regular grammars are LL(1) LR(1) I guess they can't be LL(1) because of left recursion, but ...
1
vote
1answer
99 views

Why we use context-free grammar for parsing?

Why we use context-free grammar for parsing? Why not regular expression and not context-sensitive grammar?
0
votes
2answers
115 views

Computing FOLLOW sets for LL(1) grammar. Stuck on question

Calculate the FOLLOW sets for all the non terminals: $S \rightarrow bEx \mid Db \mid b \mid F$ $D \rightarrow EDc \mid Y$ $E \rightarrow dED \mid dDY$ $Y \rightarrow ab \mid ...
0
votes
1answer
83 views

Is this grammar LALR(1)

I am working through creating a LALR(1) parser generator. I have the following grammar which I designed to highlight the epsilon for rule 3. ...
1
vote
2answers
89 views

Min-Max number of shifts and reductions in bottom-up parser [closed]

Given the Grammar has no unit or ɛ-productions, What is minimum & maximum number of shifts and reduce needed by bottom-up parser?
1
vote
2answers
51 views

How can this grammar parse such an input?

I've an example which I simply don't get at all. Implement an attributed grammar that checks that either the word ends in $b$ or each prefix of the word contains at least as many $b$s ...
-1
votes
1answer
54 views

Is this $LL(1)$ grammar valid?

Is the following a valid $LL(1)$ grammar: $ \begin{align} S &\rightarrow L \$ \\ L &\rightarrow M L_2 \\ L_2 &\rightarrow \underline{::} L \\ L_2 &\rightarrow \epsilon \\ M ...
0
votes
2answers
53 views

Relation between CLR Grammar and Ambiguity

I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous? Is it possible that a grammar which is ...
1
vote
1answer
109 views

LALR(1) parsers and the epsilon transition

I am having trouble getting my head wrapped around epsilon transitions while creating an LALR(1) parse table. Here's a grammar that recognizes any number of 'a' followed by a 'b'. 'S' is an ...
0
votes
0answers
45 views

Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

I have constructed an SLR(1) parsing table with the following rules. S -> S + S + S (rule 1) S -> S + S (rule 2) S -> y Is reducing rule 2, then shifting + and y, then again rule 2, equivalent ...
0
votes
1answer
39 views

Given family of grammars, determine if LR(k)

Parsing family of grammars, determine if LR(k) I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him ...
0
votes
1answer
58 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? ...
0
votes
2answers
190 views

Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?

This question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was, Consider the following six classes of languages: Context free ...
3
votes
2answers
400 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 ...
2
votes
1answer
157 views

Resolving ambiguity in dangling else

Initially the ambiguous grammar is as follows (with some cropped production rules): ...
4
votes
1answer
498 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
56 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
150 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
37 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 ...
0
votes
0answers
87 views
2
votes
2answers
92 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 ...
1
vote
0answers
78 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
137 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 ...
2
votes
1answer
113 views

Expressive power of lexer + parser

Most modern compilers split their syntax analysis into a lexical phase that is followed by a parsing phase. The lexical phase is given by a regular expression, while parsing is guided by a ...
2
votes
2answers
102 views

Lexing and parsing a language with juxtaposition as an operator

Normal human math notation treats juxtaposition as implied multiplication, e.g., $2x$ means $2$ multiplied by $x$. This does not seem to be a common feature of computer languages, although it was, for ...
-4
votes
1answer
67 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)
6
votes
1answer
151 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
102 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
85 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
267 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. ...
3
votes
1answer
78 views

Building Simple Parse Trees

I am trying to learn how to build parse trees. I have watched videos and tried to do some on my own, but am a little lost. In this example, I am given the following: $$ \begin{align*} &S\to(L) ...
2
votes
1answer
80 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 ...
0
votes
0answers
52 views

Parsing Turing Machine

Have a question that requires me to write the rules for parsing a turing machine This is the question The PROBLEM involves writing a set of Turing Machine rules that will read and determine whether ...
1
vote
1answer
66 views

Why does left recursion have to be eliminated? [closed]

For example, Let the Grammar be: S->Sa|B Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa What's wrong with ...