Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
19 views

Generating an “approximate” grammar

This is my first time posting here, so I hope I'm on topic. I have a table of natural-language data of the form ...
-1
votes
0answers
44 views

How do HTML parsers work? [closed]

I am coding a web scraper from scratch. This means no BeautifulSoup or Python HTML parser. From the moment you receive the GET requested information from a web page, I want to know how it becomes an ...
0
votes
0answers
15 views

Why can't I evaluate this L-Attributed SDD with a pre-order traversal?

My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either ...
0
votes
1answer
24 views

CYK algorithm in theory of computation

For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n. Doubt: I marked it false in a national level exam.I think it should be any null-free context ...
-1
votes
1answer
30 views

Compilers: how to find first and follow sets?

I sort of know how to solve the problem but I am not sure how to do it in a systematic way. Could someone provide a step-by-step solution especially for the follow set one? Thanks!
1
vote
1answer
36 views

How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?

How would the following term in the pure untyped lambda calculus be parsed: y λx.x y The relevant conventions listed on https://en.wikipedia.org/wiki/...
2
votes
0answers
15 views

Unparsing an operator grammar in the face of ambiguity

I'm using the grammar scheme of Danielsson and Norell ("Parsing Mixfix Operators"). The short version is: user defined mixfix operators such as _+_ or <...
1
vote
1answer
22 views

How to handle L-attributed SDDs with LR parsers

I've read Chapter 5, Syntax Directed Translation, of the Dragon Book but am still unable to understand the following related points: How to handle L-attributed SDDs in an LR grammar when using a tool ...
0
votes
1answer
15 views

Compilers: How to see “the number of grammars where there exists a string that has at least two different left-most derivations”?

Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?
0
votes
2answers
201 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
20 views

I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }

I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '. So far I made one that accepts T = { a, b, *, +, (, ), E}...
0
votes
1answer
36 views

Computing FOLLOW sets of left recursive grammar

Left recursive ambiguous expression Grammar: $E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$ I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
1
vote
1answer
77 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 ...
10
votes
1answer
369 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
801 views

When will SLR(1) parser fail but CLR(1) will not

Dragon book says following about where SLR(1) parser can fail but CLR(1) wont: Recall that in the SLR method, state $i$ calls for reduction by $A→α$ if the set of items $I_i$ contains item $[A→α.]$...
0
votes
0answers
29 views

What is the most commonly used/ most practical method to parse context sensitive languages?

what is the most commonly used / most practical method to parse CSLs ? By "most practical" I mean Not too theoretical but in opposite to that, with practical usecases Not too complicated (...
0
votes
1answer
9k 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
167 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
254 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
1answer
98 views

Why is XML hard to parse?

I was chatting with a friend about my love/hate relationship with XML. He made the comment that, "xml is broken primarily because parsers for recursive self-defined document are basically ...
0
votes
1answer
522 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
62 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
325 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 (...
11
votes
4answers
7k 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 ...
1
vote
0answers
22 views

Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
1
vote
1answer
111 views

Linear Grammar in less than cubic time

I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types. Is there an algorithm to determine whether $s \in L(G)$ ...
1
vote
1answer
53 views

CYK - finding the closest word accepted

Let's say I have a context-free grammar G and a string S. The normal CYK algorithm outputs that s can not be build using G. How would I find the closest String S' that can be build using G?
1
vote
1answer
109 views

What does “lookahead” refer to?

I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word. What does "lookahead" refer to? How does this relate to LL, ...
0
votes
0answers
20 views

How to convert recursive language grammar tree into automaton for optimal parsing?

So I have a definition of a sort of grammar for a programming language. Some aspects are recursive (like nesting function definitions), other parts of it are just simple non-recursive trees. ...
0
votes
0answers
18 views

Do the SLR and LALR parsers of a same CF grammar have the same shift actions?

In theory, given that: The LALR parser can be constructed by merging LR(1) states with the same core; If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$; ...
1
vote
1answer
29 views

What are cases where we cannot perform LR parsing without augmented grammar?

Many standard Compiler Design texts mention constructing augmented grammar as first step of LR parsing. The reason frequently is It is required in cases where start symbol comes on right hand of any ...
0
votes
0answers
54 views

ANTLR G4 grammer for math expression

I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below. ...
1
vote
0answers
47 views

How to write “∀x.F(x)” for “F(x)=λx.Φ(x)” in one expression (sequel from question about “∀(λφ. (φ x m→ φ y))”?

This question is sequel from How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"? which further explains the notation and context. So - I have anonymous Boolean-valued ...
1
vote
2answers
144 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
0answers
50 views

The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
0
votes
1answer
45 views

Is there any official terminology about something like double quotes “” grammar?

In many programming language string is a token. For example: ...
0
votes
1answer
106 views

Removing left factoring from Context-Free Grammar

I know that, removing left factoring is a simple task. And i understand following procedure: $S→aA | aB$ Becomes: $S→aS'$ $S'→A|B$ Yet I'm running into problems with this particular grammar: $S→AD|...
0
votes
0answers
44 views

Turning grammar to LL(1)

I have difficulty / doubt in transforming a grammar into LL (1), I tried remove left recursion but grammar still not LL(1). ...
1
vote
1answer
62 views

Why is the following grammar not LL(1)

Consider the following grammar: S → bAb | bBa A → aS | CB B → b | Bc C → c | cC I have to provide the reasons as to why this grammar is not LL(1). So far ...
0
votes
0answers
23 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
0answers
345 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 ...
2
votes
1answer
966 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
0answers
25 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
31 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 ...
3
votes
1answer
92 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
28 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
28 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
66 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 ...
-2
votes
1answer
37 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
36 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
2 3 4 5
8