Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
-4
votes
0answers
25 views

Can someone send the solution

For the grammar Sa S a | aa construct LL parsing table and show how string “aaaaaa” is parsed in top down parser
0
votes
0answers
21 views

Disposition: Parsing

I have to prepare 30 minutes of oral examen about the subject called parsing. Where I have to talk about it. And then I shall hand in like 30 pages (including code and figures etc). I don't know how ...
0
votes
2answers
46 views

Is this an LL(1) grammar? How to solve First - Follow conflict?

im trying to check if this grammar is LL(1). S -> L = R L -> * L | id R -> L | R + R | num As you can see there is a Left recursion on R production. So i remove that and what i get is: S -> L = ...
0
votes
0answers
201 views

Convert Source Code into English Text?

Is there a way to convert, i.e., C code into English? The purpose would be to convert source code into a Text-To-Speech converter which would enable someone to "listen" to source code. EDIT: An ...
0
votes
1answer
413 views

What is the Purpose of Augmented Grammar in LR parsers?

I was reading the LR() parsers from the Dragon Book where I came across these lines: To construct canonical LR(0) collection for a grammar, we define an augmented grammar and 2 functions, CLOSURE ...
0
votes
1answer
67 views

SLR(1) Table construction, FIRST and FOLLOWS

when constructing the SLR(1) table for some grammar I need to compute the FOLLOW set for all terminals in order to decide where and when to reduce. Do I compute theme for the augmented grammar or ...
0
votes
0answers
16 views

Computing Follow sets of Grammar for LL(1) parser

I am trying to compute the Follow set of the following Grammar: E -> E' E A A -> + | * E -> num E' -> num I start by adding the end of string symbol, ...
1
vote
2answers
27 views

Retrieving data from website - Parser vs AI

I'm currently working on a personal software project (as a hobby) and would like to know which kind of approach I should follow according to you. My application scans some websites (like Amazon or ...
2
votes
1answer
76 views

Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that ...
0
votes
1answer
22 views

how to formally arrive at a correct EBNF grammar of a language

I am trying to write a mini parser for a simple language whose specification is as follows: A search term is represented by. Both searchkey and ...
1
vote
1answer
22 views

Grammar still ambigous after removing left recursion LL(1)

I have following grammar it doesnt not have Epsilon-derivation problem I can only see left recursion: S -> a b S S -> S a b S -> c d S -> a d in ...
0
votes
1answer
43 views

What is the time complexity of finding the FIRST and FOLLOW sets?

Given how important these are for parsing, I'm surprised I wasn't able to find anything about their complexity. I'm interested in all combinations of: What is the (edit: best known) time complexity ...
10
votes
1answer
350 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
-2
votes
1answer
34 views

Computing FIRST and FOLLOW

Given the following grammar with terminals $VT=\{[,],a,b,c,+,-\}:$ $S \rightarrow [SX]|a$ $X \rightarrow +SY|Yb|\epsilon$ $Y \rightarrow -SXc|\epsilon$ This should be the FIRST function: $first(S) =...
0
votes
0answers
18 views

Abstract syntax tree: expression->operation->lhs|rhs vs expression->lhs|operation|rhs - what should I take into account in decision?

I am trying to build class hierarchy for the abstract syntax tree of First Order Logic as specified in the grammar https://github.com/antlr/grammars-v4/blob/master/fol/fol.g4 (ANTLR parser generator). ...
1
vote
1answer
25 views

Defining Grammar for Given Language

I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-...
0
votes
1answer
8k views

LL(1) parsing table construction

i have the following CFG E -> ABC A-> a|Cb|epsilon B-> c|xA|epsilon C-> y|z and the First of the Non-Terminal : ...
0
votes
1answer
95 views

LR(1) parsing, problem with look ahead symbols

I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution. I'm trying to fill the LR(1) parsing table for the grammar ...
2
votes
1answer
985 views

Indirect Left recursion

I'm resolving indirect left recursion for these production rules: S -> Aa / a eq1 A -> Sb / b. eq2 Where S is the ...
0
votes
1answer
2k 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 computing the follow set specifically for the empty word. Given the grammar: ...
2
votes
1answer
223 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 ; ...
1
vote
2answers
124 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 ...
1
vote
1answer
48 views

Would the following grammar be ambiguous?

I have the grammar $S = aSbS|bSaS|\varepsilon$. When I was first looking at the problem I thought it was unambiguous. When I looked at the answer it said that it was ambiguous. The solution it gave ...
0
votes
1answer
38 views

Grammars and Parsing: Ambiguity in Sequences

BACKGROUND I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches. Given terminals: "a": KEYWORD "b": ...
0
votes
1answer
18 views

Why shift means push terminal symbol and state into the stack? Why not push only state?

Shift means that you need to put the status and terminal symbol on the stack. But what is the terminal symbol used for? After all, if the reduce command is executed, both the state and the terminal ...
1
vote
1answer
31 views

Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?

I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars. However, I've encountered this statement from my notes: With $\epsilon$ productions in the ...
0
votes
1answer
31 views

How can I determine the start non-terminal of a CFG?

Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (disjoint). $A ::= x|y|z$ $B ::= a|b|c$ ... $...
0
votes
1answer
443 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 \...
3
votes
3answers
3k 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\mid n,m\in\mathbb N,\>n\ge m\,\}$$ Is my hypothesis true ...
1
vote
1answer
54 views

Why table-driven LL (1) parser does not work with division and subtraction?

Everywhere, one grammar is used as an example table-driven LL(1) parser. Grammar ...
0
votes
1answer
21 views

Build LL(1) parsing table for grammar S -> iSeS | iS | a

Task Bulid parsing table for grammar S -> iSeS | iS | a Resolve conflicts in this table and simulate parser work for word ...
2
votes
1answer
129 views

What is the relation between parsing languages and checking languages?

I have looked at a number of textbooks on computability theory. They typically have the following form: Define a language class (regular, context-free, context-sensitive, recursively enumerable) ...
10
votes
3answers
2k views

Representing “but not” in formal grammar

I just came across the following grammar definition: CommentChar ::       SourceCharacter but not LineTerminator But for discussion, I'll present this similar ...
0
votes
1answer
48 views

CYK result de-transformation

Suppose we have a rules derived from a treebank. And in order to get a syntax tree of a given sentence we use the cyk algorithm. In order to use the cyk we should convert the rules into chomsky normal ...
0
votes
1answer
141 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
-1
votes
1answer
50 views

How do you define and parse variables (free or bound) from user-entered strings?

I'm writing an application in which the user might enter expressions such as $\text{lim}_{i \in I} \beta(i)$ where $\beta$ is a functor. That's just an example, the expressions, which contain ...
3
votes
0answers
36 views

Algorithm for undirected projective dependency parsing

I am looking for an algorithm that will get an optimal projective undirected dependency parse. That is, given the sentence 'Mary does love John', and an edge-weight function $f$ (that is, a function ...
0
votes
1answer
55 views

Which parser has the highest reduce moves?

From what I have learned the number of reducing moves in the parsers are generally in the order LR(0)>= SLR(1) >= LALR(1). But I am unable to understand where should I place CLR(1) in this ...
0
votes
1answer
20 views

How to create a LR(k) grammar for an arbitrary k

Is there a simple procedure for constructing a grammar that is LR(k) but not LR(k-1) for any k?
4
votes
2answers
471 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
0
votes
0answers
21 views

Find equivalent LL(1) grammar

There is sample question to calculate equivalent LL(1) grammar for below grammar: $S \rightarrow S b$ $S \rightarrow S d$ $S \rightarrow c S$ $S \rightarrow c c a$ At first step, ...
0
votes
0answers
30 views

Is this correct transformation of a grammar to one without left recursion?

So the last few days I am writing a compiler for a subset of C language by given grammar for a class at university. I encountered this problem and then I realized I need to remove left-recursion in my ...
0
votes
2answers
54 views

Is this correct grammar definition of Backus-Naur form?

I've been given a grammar definition of "Simple C language" in Backus-Naur to write a compiler for a class assignment. I've been trying to implement the parser for some time now and I just can't move ...
0
votes
0answers
11 views

Detect a class of a grammar having its DSL AST

I have a grammar for some language written in some DSL for writing grammars, and this DSL implements EBNF. I have an AST for the description of a grammar in the DSL. How can I detect the minimal class ...
0
votes
1answer
144 views

Is following grammar LR(0)?

I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question. Grammar: $SL \rightarrow SL ; S \space | \space \epsilon$ $S \...
2
votes
1answer
362 views

What's wrong with this LL(1) grammar?

I am trying to build a LL(1) parse table for the following grammar: S -> L L -> L : L L -> id R R -> ( L ) R -> ( ) R -> Epsilon There are two ...
3
votes
1answer
178 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 ...
0
votes
1answer
87 views

Pushdown automaton from given code for parsing a while statement

I was preparing for my exam and have some questions that can possibly come on the test. There is a task to make pushdown automata from a given code: ...
0
votes
1answer
31 views

To remove all comments in a JavaScript file, do we need just a scanner or also a parser?

I was asked how to remove comments in a JavaScript program, but once I gave the regular expression solution, I was asked what if there are comments like text inside of a string: ...
14
votes
2answers
2k 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 ...

1
2 3 4 5
8