Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
3
votes
0answers
27 views

How to model grammar ambiguity

Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings. Practically, ...
2
votes
0answers
254 views

SLR vs CLR parser

In SLR we use follow set of a non terminal for determining reduce moves and in CLR we use lookaheads for the same. How does using lookaheads actually help in improving the performance of the parser ? ...
1
vote
0answers
118 views

The upper bound on a Nondeterministic Finite Automata's configurations number

In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon, in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2, section "Equivalence of NFAs and DFAs" discusses the upper bound of a NFA's ...
1
vote
0answers
128 views

Can the HTML5 parsing algorithm be implemented in linear time?

Can the HTML5 parsing algorithm (https://html.spec.whatwg.org/multipage/parsing.html#parsing) be implemented in $O(n)$, or at worst $O(n\mathop{log}n)$, time, even for malicious input? It seems ...
1
vote
0answers
80 views

Where is left recursion in this little CF grammar?

S → D D → E | EC E → anyId C → B | .D | B.D B → <S> | <SA> A → ,S | ,SA The tool I am using keeps complaining about left recursion in this grammar. I ...
1
vote
4answers
1k views

Eliminating cycles from a grammar

I have the following grammar: S -> Xb | Y Y -> X | a X -> S | c Here the lowercase letters are terminals. I have an algorithm to find the cycle in ...
13
votes
3answers
1k views

What would you get if you add parameters to context free grammars?

I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python ...
1
vote
0answers
154 views

Is the Java 8 Grammar still a LALR(1) grammar?

As I found out here: http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html , the Java Version of 2005 (might be Java 6, I'm not sure) is a LALR(1) grammar. However, I couldn't ...
0
votes
1answer
214 views

Neither Left nor Rightmost Derivations

Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the ...
1
vote
0answers
41 views

Determining the set of valid next terminals when generating from a CFG

I am trying to generate random sentences from a context-free grammar. During each step, the next non-terminal to be generated is determined according to some probabilistic criteria irrelevant to this ...
8
votes
2answers
921 views
2
votes
0answers
152 views

How would I build a parser generator for a context free grammar using Pushdown Automata?

I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc. I am at the point where I have lexer generation ...
2
votes
1answer
320 views

Understanding context free grammars in conjunction with PDA

I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really ...
3
votes
1answer
1k views

How to generate an LL(2) parse table?

The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that: ...
1
vote
0answers
165 views

Converting Ambiguous Grammar G to LL(1)

So I am in the process of learning about LL(1) grammar and converting an ambiguous one into LL(1). I know how to figure out if a grammar (G) is ambiguous, however, I am having trouble converting it to ...
3
votes
1answer
208 views

If a grammar is SLR(1) then are the LALR and SLR tables the same?

I think they are because, SLR and LALR have same number of states and, since there are no conflicts in SLR table this means all the SLR information is needed and correctly used for parsing, so all ...
1
vote
1answer
218 views

Choosing a production with $\lambda$ in Context-Free Grammars

Given the context-free grammar \begin{align*} & S \rightarrow AA \\ & A \rightarrow xA \\ & A \rightarrow B \\ & B \rightarrow yB \\ & B \rightarrow \lambda \end{align*} What is ...
4
votes
1answer
424 views

How to find unambiguous grammar for palindromes

I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc. ...
0
votes
0answers
46 views

Is Kalman filter used in automata (besides cellular automata) and parsing grammars?

I am new to Kalman filter and parsers. I understand that it's suitable for prediction/estimation on the go, when you have something to measure (not only the model), and when changes always occur in ...
9
votes
2answers
700 views

Is there a different resolution of the “dangling else” problem other than “match closest”?

The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for ...
0
votes
0answers
999 views

Difference between LR parsing and Shift-Reduce parsing?

I'm learning natural language processing and I can't understand the difference between Shift-Reduce parser and LR parser. As I've understood from Wikipedia, shift-reduce is just a name of a class of ...
3
votes
2answers
2k views

Bottom-Up Evaluation of Inherited Attributes

I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows : Using a top-down translation scheme, we can implement any $L$-attributed definition ...
0
votes
0answers
212 views

Is this depth-first top-down parsing algorithm a recursive descent top-down parsing algorithm?

In Thomas Sudkamp's book, Machine and Languages, there is a depth-first top-down parsing algorithm (please see the algorithm here). My main question is: 1) Is this algorithm a (backtracking) ...
0
votes
2answers
476 views

Is the given grammar LL(2)?

http://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf The book by Grune and Jacobs presents an example of a grammar that is $LL(K + 1)$ but not $LL(K)$ The example is $S -> a^kb/a^ka$ The ...
3
votes
1answer
560 views

Eliminate left recursion from grammar

Consider the following grammar: $$ A\to Ba|Aa|c \\ B\to Bb|Ab|d $$ How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion? I have tried applying the ...
0
votes
1answer
4k 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 : ...
2
votes
4answers
457 views

How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?

$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt $\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt $\mid \textbf{...
4
votes
1answer
580 views

Bottom-Up Parser With Leftmost Derivation

I'm reading the book Parsing Techniques by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization: [...] a parser can produce a list of ...
1
vote
1answer
251 views

boolean expression syntax checking

i am trying to formulate an algorithm for syntax checking for simple boolean expression like (var1 = 10) or (var2 > 100). evaluation part seems to be easy as i will convert infix to postfix and ...
0
votes
0answers
89 views

Is grammar S→aaab | aab in LL(2) but not SLL(2)?

I'm trying to figure out how to create grammars which are LL(k) and not SLL(i). Is this grammar LL(2) and not SLL(2)? $S \to aaab \mid aab$ Where S is a starting symbol. I think it is not SLL: ...
1
vote
0answers
59 views

Is it possible to transform this grammar into LL(1)?

This is the original grammar: S -> ABe A -> ab | a | ϵ B -> b I did try left factoring and this is what I got: ...
2
votes
3answers
408 views

Simple question about grammar derivations

I'm learning the basics of grammars and compilers for a comparative programming languages class, but having a bit of trouble with one aspect of grammar derivation. Here is an example of a grammar ...
3
votes
0answers
98 views

Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?

Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing? The ...
2
votes
1answer
1k views

Shunting Yard Algorithm extension and AST generation

Let me introduce you to my current project (that obviously yields the problem I face hence I post here). I am writing a so-called "compiler" for a simplistic language. I have already built a VM ...
0
votes
1answer
43 views

Can I mix LL and LR parsing?

I want to go RD parsing with Shunting Yard for expression (for the sake of easier operator precedences and less left-recusion), is that considered no-good because nobody did that before?
6
votes
2answers
276 views

any hope for a universal automatic parser?

Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and ...
4
votes
1answer
339 views

Parsing CFLs (simulating PDA vs CYK algorithm)

We can simulate the PDA and parse the language with the following operations (vaguely): Read the input symbol and top of stack - $O(1)$ Check all the transition rules (must check all for non-...
2
votes
0answers
54 views

Correct bracketing check with rotate operation on position i

Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations: Check whether the sequence is correctly bracketed Rotate bracket ...
0
votes
1answer
83 views

Context Free Grammar for Try-Catch-Finally Statement and Throw

I am currently working on a problem that is asking me to write the grammar productions for the try-catch-finally and throw C# statements. It states that "you can assume that there are nonterminals "...
3
votes
1answer
1k views

White-space and comment by lexical analyzer

Lexical Analyzer mostly deletes comments and white-spaces. One example where I think Lexical Analyzer might not be discarding white-spaces is in Python language, as indentation has a important role in ...
5
votes
1answer
942 views

Check for balanced parentheses in an expression in log-space

Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in the expression. For ...
4
votes
3answers
860 views

Streaming parsing algorithms

A parser is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree. Let a streaming parser be a parser which for any prefix $u$ can ...
0
votes
1answer
2k views

Conditions for LL(1) grammar

One of the conditions for A → α | β to be LL(1) grammar states that If β → ε in one or more steps then α doesn't derive any string beginning with a terminal in FOLLOW(A). Likewise If α → ε in one ...
1
vote
1answer
345 views

What is a “special sequence” in EBNF?

In Extended Backus-Naur Form (EBNF) there is one form called a "special sequence" which is surrounded by questions marks ?...? What does this mean?
0
votes
2answers
465 views

Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
2
votes
1answer
188 views

Does my grammar contradict LL ⊆ LR(1)?

This answer claims that $ LL \subseteq LR \left( 1 \right )$ where $LL = \bigcup_k LL(k)$. But is this true? Is this grammar a valid counterexample? $ S \rightarrow a | Aaa $, $ A \rightarrow \...
0
votes
1answer
69 views

Is there any precedence for symbols for constructing parse trees? [duplicate]

I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees. For example, the sentence: p ∧ q → r, ...
6
votes
1answer
613 views

What would a formal grammar for a binary file format look like?

Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive. What would ...
0
votes
1answer
32 views

Unsure about parse tree of PCFG

I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa. My solution would look like ...
1
vote
1answer
42 views

Why is particular token missing in LALR lookahead set?

I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin: S' ::= S S ::= L = R | R L ::= * R | id R ::= L The items associated ...