Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

-2
votes
0answers
17 views

CYK vs Earley algorithm [on hold]

What are the differences between CYK and Earley algorithms? Please provide a thorough rundown.
-4
votes
0answers
13 views

Complexity of CYK algorithm [on hold]

What is the Big O complexity of the CYK ( Cocke–Younger–Kasami ) algorithm as a function of the size of grammar G?
1
vote
0answers
25 views

How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.(\| is the escape character, since | is a special character in grammar's pattern). ...
0
votes
1answer
43 views

Proof that the grammar is LL(2)

I am given the following grammar: $ S \rightarrow AabAba \\ A \rightarrow a | \epsilon $ and I have to prove it is LL(2). I know what LL(k) means - one can choose a production based on k characters ...
1
vote
1answer
11 views

Why can't exhaustive search parsing stop after |w| + 1 derivations?

If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in ...
1
vote
1answer
10 views

Choosing correct action in bottom up parsing

Using grammar: $ S \to aABe \\ A \to bcA \mid c \\ B \to b $ to bottom parse a string $abcccde$, the course of action would be: $ \begin{array}{c|c|c|c} \hline Step & Stack & Input &...
2
votes
0answers
27 views

How to know a certain grammar is parse-able

Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it. ...
1
vote
2answers
23 views

How to determine maximum stack size of LL(1) parser?

I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by ...
2
votes
1answer
70 views

What was Robert Floyd's algorithm for inserting brackets?

In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other ...
1
vote
1answer
46 views

What is handle in bottom up LR parsing?

I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows: Assume a rightmost ...
1
vote
1answer
83 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
2
votes
1answer
20 views

Marginalise edge weights on graph

I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a ...
0
votes
1answer
50 views

Can you automatically generate a parser for a type using type theory some how?

Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?
6
votes
1answer
50 views

Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

The problem of determining, given a string $x$ and a context-free grammar $G$, whether $x \in L(G)$ is conjectured to take more than linear time in the length of $x$. Currently the best known ...
1
vote
0answers
77 views

Are LL(1) grammars a subset of LR(0) grammars?

As far as I've understood it seems that LL1 are a subset of LR0, but studying the following grammar I end up in a contraddiction. Grammar : S -> (S) | [S] | {S} | ε This is an LL1 while it seems ...
1
vote
1answer
23 views
0
votes
0answers
37 views

Transform grammar into LL(1) left-associative

I was looking on some old exam questions for a course in my university, and stumbled upon an exercise that asked for the following: The starting grammar was this: ...
0
votes
1answer
35 views

What is Follow(X) when there's a rule, A -> XBCD where First(B) and First(C) contain empty, but First(D) do not

I have a question about follow sets. Suppose there's a rule, A -> XBCD B -> $\beta$ | $\epsilon$ C -> $\gamma$ | $\epsilon$ D -> $\delta$ What is Follow(X)? Is it (First(B) - $\...
2
votes
0answers
18 views

Expanding an Earley parse forest

I have a small context-free grammar, which I would like to use to turn input strings into parse trees. I need to get all possibilities in case of ambiguity (so shift-reduce is out), and there's quite ...
1
vote
1answer
33 views

How do I build a left derivation tree from an expression including right-to-left associativity?

Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? ...
0
votes
1answer
29 views

Can we use Operator precedence parsing with this grammar?

This Grammar: A-->Bbab|aa B-->b I think we can't because basically there is no relation between terminals? like no relation between a and b! or am i missing something? and the language of this ...
-1
votes
1answer
20 views

Parsing table confusion [closed]

I've been researching the different answers I've been given to this, would somebody just be able to give me a clear answer of the difference between Shift, reduce and go-to. - In a parsing table. Of ...
3
votes
1answer
102 views

Is there a name for this tree traversal?

This came when I was looking at block scoping in compiler design. { A { B } { C {D} {E} } } For the above pseudo code, the order in which the scope ...
1
vote
0answers
108 views

Can a YACC parse an ambiguous grammar

I found a question while studying compilers :- Given a grammar E->E+E/E×E/number The above grammar is fed to a YACC with semantic rules for parsing. What will be the action of the YACC. 1) it ...
0
votes
0answers
26 views

Name for a property of grammars

Parsing s-expressions is almost trivial. This is true for both automated processes (and thus implies ease of implementation of such processes) and for a human readers of printed s-expressions. It is ...
2
votes
1answer
87 views

Why doesn't the C/C++ compilers create different tokens for different types of numbers?

Based on GeeksforGeeks and many other sites, the C/C++ compilers will create the same token for float/int etc. However if we ...
2
votes
1answer
73 views

Should we eliminate left recursion before using NPDA to simulate CFG?

I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser". It says: If a language is context free, then some pushdown automaton recognizes it. Let A be a ...
1
vote
0answers
31 views

Generate an AST from an indefinite grammar and logic

As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a ...
1
vote
1answer
30 views

Formalism for unambiguous context-sensitive languages?

I know that there are some languages that are unambiguous but not context-free (this is a good fact). Is there any kind of formalism for describing unambiguous context-sensitive languages? Even better ...
0
votes
0answers
20 views

Defining LL(1) grammar

I am having difficulty finding a good example and definition for LL(1). I do understand what LL stands for. My problem is (1) part. A lot of them mention the "# of look-ahead tokens/symbols" Can ...
0
votes
1answer
28 views

extend ECMAScript by adding new keywords and syntax

I would like to extend ECMAScript by adding new keywords and syntax to it, for example: |variableName| stipulates a special kind of variable which I would like to be able to include in a normal ...
2
votes
1answer
83 views

Conversion of ambiguous left recursive grammar to LL(1)

I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar $ G = \left\{V_N, V_T, S, \Phi \right\}$, with the non-terminal ...
0
votes
1answer
33 views

How to define whitespace for certain rules but else ignore it

I am trying to make a programming language for the first time and wonder how it handles whitespace. I can see CFG by default seem to just ignore whitespaces, but what if I want it to use it sometimes? ...
1
vote
1answer
79 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
0
votes
1answer
33 views

Best Approach To Parse Human Readable Text To Machine Readable (CSV)

I am attempting to parse a large amount of text that cannot be readily used by other software due to the human readable design. However, each "section" of the text has the same format. By "section", I ...
1
vote
3answers
447 views

Dangling else problem

I was reading a book about compiler design, then in the CFG section, they introduced the dangling-else problem. They offered to match the the else with the last <...
2
votes
0answers
49 views

Examples of context-free grammars with worst-case complexity

What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers? I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would ...
0
votes
0answers
81 views

How do we evaluate semantic actions in L attributed SDT?

I came across following problem: $S→ER$ $R→∗E\{print(′∗′);\}R∣ε$ $E→F+E\{print(′+′);\}∣F$ $F→(S)∣id\{print(id.value);\}$ Here $id$ is a token that represents an integer and $id.value$ ...
0
votes
1answer
74 views

Not getting the clear picture of Goto actions , reduce and shift actions in SLR Parsing

I am going through the following lecture notes on LR parsing : https://www3.nd.edu/~dthain/courses/cse40243/fall2016/chapter4b.pdf For the following grammar : The following LR automation has been ...
2
votes
1answer
63 views

Is there a way to efficiently parse this grammar?

Consider the following context-free grammar: $T \to (*) \mid (T*) \mid (*T) \mid (T*T)$ This effectively forms a notation for binary trees: A binary tree is a $*$, with optional children on either ...
2
votes
1answer
242 views

Number of nodes of a parse tree when the Grammar is in CNF?

There happened to be a following question - In any Chomsky Normal Form grammar $G$, how many nodes will all parse trees for terminal strings of length $n>0$ generated by G have? I tried for ...
1
vote
1answer
34 views

Follow set confusion about inclusion

The book I am learning about compilers from states that $M \to \alpha N \beta$ will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable. This ...
1
vote
1answer
155 views

Tokenization Problem

Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult. My Regular ...
0
votes
0answers
28 views

Is this language $LL(1)$ parseable?

$$L = \{(a,b)^* \mid \text{#a's } = \text{#b's}\}$$ I tried some grammars like: $ S \rightarrow aSbS \mid bSaS \mid \varepsilon $ But it is not $LL(1)$ because $FIRST(S) \cap FOLLOW(S) \ne \...
0
votes
0answers
40 views

How to count constituents in PARSEVAL?

I have a doubt in PARSEVAL. Consider the picture below: I am not able to understand why constituents like NNS, VBD, VBG, DT, etc. have not been considered in calculating the recall and precision. The ...
0
votes
1answer
163 views

LL1 parsing algorithm for strings generated by a given grammar

How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar? I have to design a parser for a specific grammar. Let $G$ be the grammar described as: $$S \...
0
votes
1answer
143 views

How to build a parser for syntactic analysis of regular expressions?

Is it possible to build a parsing algorithm that build a parse tree using a top-down method that simulate a derivation process for regular expressions, like we do for type 2 languages? My guess ...
0
votes
1answer
680 views

What is a “sentential form”?

I do know what a "left-most-" and a "right-most derivation" is, but I stumble across the term "sentential form" and its specific differences "right-sentential form" as well as "left-sentential form" ...
0
votes
1answer
52 views

Compiler Question : Does the parser detect Errors in these examples or the Semantic routine?

For example, which part will detect these errors, Parser or Semantic Routine? 1) int Array[10.5] ( wrong size ) 2) int x="some string" 3) A[10.5] + 3 (not in declaration, but in the middle of ...
0
votes
2answers
39 views

What does the $^*$ operator do in the theory of parsing?

I'm currently reading through Aho's "Theory of parsing, translation and compiling" on my own and I got a bit confused about the closure operator on language $L$ with alphabet $\Sigma$ ($L^*$). The ...