Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
38 views

Can Shared Packed Parse Forest have more than 2 families?

I am implementing Earley parser and using algorithm from Elizabeth Scott's paper "SPPF-Style Parsing From Earley Recognisers" (section 4). Author says A family of children of u will consist ...
Somnium's user avatar
  • 275
1 vote
0 answers
16 views

Number of DCFG parse tree nodes with respect to input length

I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
Petr Skocik's user avatar
1 vote
0 answers
20 views

Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere

Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
Alex Flint's user avatar
0 votes
0 answers
15 views

Mixfix-parser: finding associated tokens on a list

I've been trying to design an in-program programming language. Like any programming language, the input source code must go through various stages: Divide the source code into tokens. (Tokenizer) ...
Microfractal's user avatar
1 vote
0 answers
48 views

How need help to specify a grammar for arithmetic expressions

I am trying to come up with a grammar for arithmetic expressions with the following order of operations: Parentheses Factorials Exponents Functions / unary plus and minus Juxtaposition (implied ...
Chris_F's user avatar
  • 111
0 votes
0 answers
17 views

Would it be fair to describing a parser generator as a functional language?

I'm playing around with the implementation of PEGs and it struct me that the parser generator itself isn't any different than the language it's use to construct. If fact, it has all of the hallmarks ...
guidoism's user avatar
  • 131
0 votes
0 answers
24 views

Any reference implementation of PCC algorithm out there?

Currently I'm exploring LALR(1) lookahead generation algorithms to implement. I've implemented Aho and Ullman one from their textbook, but recently stumbled upon "A new analysis of LALR ...
Sunfline's user avatar
0 votes
1 answer
166 views

Is this grammar LL(1) and what is it's parsing table?

Let G be a grammar with non-terminal A, terminal a and these productions: A -> A a It is ...
Ian Rehwinkel's user avatar
0 votes
0 answers
74 views

What is the simplest parsing algorithm?

I want to learn more about parsing techniques, and to do that I'd like to start with the simplest algorithm, understand its limitations, and progress from there. From what I've seen, the best ...
user avatar
0 votes
0 answers
45 views

Which language can be parsed recursive descent?

We consider languages over the alphabet {a,b,c}. Given a character t in the alphabet and a non-negative integer j, by t^j we mean the string consisting of exactly j occurrences of t. Now let m be an ...
ee ss's user avatar
  • 3
0 votes
1 answer
66 views

Can all LL(k) grammar can be recognized by LR(1)?

For context free languages, I wonder that if all LL(k) languages can be recognized by a LR(1) grammar?
xie cui's user avatar
1 vote
1 answer
41 views

Equivalence of LR(k) and LL(k′) parsers

Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?
Gator's user avatar
  • 11
1 vote
1 answer
27 views

Constrained precedence parsing

This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem? The setup is as follows: we are given $n$ ...
Mario Carneiro's user avatar
1 vote
1 answer
36 views

How do you convert a string representing a finite set of strings into a regulair expression without using lots of vertical bars?

Consider the following string: ...
Toothpick Anemone's user avatar
0 votes
1 answer
60 views

Parsing algorithms

I have experimented with a grammar that I could turn into a strict left-to-right finite state automaton driven algorithm (bottom up, table driven). The FSA could be complex, that's not a problem. It ...
Gunther Schadow's user avatar
2 votes
0 answers
120 views

How to write a grammar with a low-precedence unary postfix operator?

Like this person on Google Groups, I'm trying to understand how to write a grammar involving Wolfram Language's low-precedence unary & operator. The operator ...
ForceBru's user avatar
  • 121
0 votes
0 answers
34 views

First Set for this grammar? Is it Indirect Left-recursive

Given the grammar (Uppercase alphabet is non-terminal, lower-case alphabet is terminal), how to find FIRST set? A -> mB | CD B -> CBn | epsilon C -> pA | epsilon D -> q This is NOT a ...
vfg's user avatar
  • 1
0 votes
1 answer
59 views

How to make LR(1) grammar for sequence that cannot have more "Up" than "Down" for any given prefix?

I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules: Consider a robot arm that accepts two commands: $\triangledown$ puts an apple in the bag and $\...
Dean DeRosa's user avatar
2 votes
0 answers
137 views

Determining when a substring has a unique parse forest

Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending ...
breandan's user avatar
0 votes
1 answer
44 views

Why is flex the best choice for handling mathematical content? (a question about approach0)

This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation. Mr. Wei Zhong uses flex lexer generator. Now, supose I find an ...
R. S.'s user avatar
  • 157
0 votes
1 answer
86 views

Why is a LALR parser the correct choice for parsing mathematical content? (a question about Approach0)

This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation. The parser used by Wei Zhong is LALR. Now, supose I have to parse a ...
R. S.'s user avatar
  • 157
0 votes
1 answer
56 views

Generating parse trees when only a recognizer is given

I am trying to understand "On the complexity of general context-free language parsing and recognition" by Walter L. Ruzzo. One of the results from the paper is about generating a parse tree ...
Rahul Gopinath's user avatar
0 votes
1 answer
56 views

Are there any updates to CYK parsing that handles epsilon rules in arbitrary nonterminals?

I am a researcher starting to work on the field of parsing and recognition of languages. As part of my background research, I am reading up on CYK. I understand that it requires the grammar to be in ...
Rahul Gopinath's user avatar
0 votes
1 answer
455 views

SLR parse table construction for left recursive grammar

I have this grammar: E -> E + T E -> T T -> T * F T -> F F -> ( E ) F -> id And this is the state diagram for it: I tried to construct a parse ...
Node.JS's user avatar
  • 101
0 votes
1 answer
93 views

Simple description of the LR(0) table generator algorithm?

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
Gunther Schadow's user avatar
2 votes
0 answers
38 views

In GLL generated SPPF graph, how does the algorithm produce children with only one parent?

I am working through (1) "GLL Parsing" (2) "GLL parse-tree generation" and (3) "Structuring the GLL parsing algorithm for performance" by Elizabeth Scott and Adrian ...
Rahul Gopinath's user avatar
0 votes
0 answers
51 views

what are all the ways of delimiting blocks

To my knowledge, in block-structured programming languages, there are 2, maybe 3 main ways of delimiting a block. Using start and end tokens, this can be brackets or reserved words etc Using ...
StackMachine's user avatar
0 votes
1 answer
422 views

Should I lookahead in the lexer or parser?

So I have this Recursive Descent Parser which outputs a Syntax Tree for arithmetic expressions. While doing some reading, I learned that LL(1) grammars have a lookahead of 1 - I remembered using a ...
dumbPotato21's user avatar
1 vote
1 answer
127 views

Can CYK algorithm be used even if the grammar is ambiguous?

Can CYK algorithm be used for ambiguous context free grammar?
Chaitanya Kale's user avatar
0 votes
1 answer
86 views

What is bottom-up pattern matching?

On the website for the book Modern Compiler Design, it is claimed that: [The book] recognizes lexical analysis, LR parsing and BURS code generation as instances of bottom-up pattern matching and ...
hkBst's user avatar
  • 133
0 votes
1 answer
88 views

Why do we retain A->.aA,a/b in I3 stage of LALR parsing of S->AA, A->aA|B?

The question is LALR(1) parsing of the following: S->AA A->aA A->b The link to the question is on this page:https://www.javatpoint.com/lalr-1-parsing My ...
Thales's user avatar
  • 103
2 votes
1 answer
137 views

What role does an asterisk serve in Backus–Naur Normal Form?

Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form What does the asterisk (*) mean? In the example below, ...
Toothpick Anemone's user avatar
0 votes
1 answer
100 views

How can we escape the pipe character in Backus–Naur Normal Form?

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form How can you distinguish between the pipe character as symbol in C++ or ...
Toothpick Anemone's user avatar
1 vote
1 answer
53 views

Getting something wrong while building parse table for the grammar

Task Build the Parse Table Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} E &\to TE' \\ E' &\to +TE'\; |\; \epsilon \\ T &\to F T' \; \\ T' &\to *FT'|\;\;\...
bigstreet's user avatar
0 votes
0 answers
31 views

Canonicalizing Arbitrary EBNF Expressions

From what I understand, LL and LR parsing require a grammar to be in "canonical form", i.e. only productions of the form A -> b1 b2 ... bn, where ...
Federico Mantovani's user avatar
-1 votes
1 answer
218 views

Argument for an $\epsilon$ free LL(1) grammar being in LR(0)?

I am trying to understand the reason as given in this answer If an ε-free grammar is not LR(0), then there is some state with both a shift and a reduce action. Since the grammar is ε-free, that state ...
user2277550's user avatar
1 vote
1 answer
29 views

Edit distance into a DCFL

I would like to generate helpful parser errors, telling the user how to fix their program. Specifically I have a deterministic context-free language $L$, given in the form of an $LR(1)$ grammar. I ...
Jonas Kölker's user avatar
1 vote
1 answer
2k views

How is the lookahead for an LR(1) automaton computed?

I'm reading Douglas Thain's book called "Introduction to Compilers and Language Design" and I've come across the following grammar: , with the following LR(1) automaton: , and I am not ...
alexandrosangeli's user avatar
-1 votes
1 answer
325 views

What is the time complexity of SLR and LALR parsers?

What is the difference between time complexity of SLR(k) and SLR(1)? and also what about LALR(k) and LALR(1)? How can I calculate time complexity of parsers? I think time complexity of LR(k) is O(n) ...
Mahla Kazemzadeh's user avatar
0 votes
2 answers
564 views

LR(1) grammar that can not be transformed an LL(1) grammar

Looking for an example of a LR(1) grammar that can not be turned into an LL(1) grammar that parsers the same language.
clinux's user avatar
  • 247
2 votes
1 answer
201 views

Strategy to designing grammar for a LR(1) parser

Is it better to think about tokens from right to left and perform right factoring on grammar for an LR(1) parser? As apposed to thinking about tokens left to right and doing left factoring on grammar ...
clinux's user avatar
  • 247
1 vote
0 answers
270 views

Relation between left derivations, right derivations and number of parse trees?

I saw this question on a test-prep site Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees? ...
user2277550's user avatar
1 vote
1 answer
55 views

How is the lookahead set computed for the Earley algorithm?

I read the dissertation [1] and the paper [2], but I'm not sure how to compute $H_{k}$. $H_{k}$ is defined as: $$H_{k}(\gamma) = \{ \alpha | \alpha \text{ is terminal,} |\alpha| = k \text{ and } \...
Augusto Hack's user avatar
3 votes
2 answers
381 views

LALR(1) grammar for simple math parser

I am trying to write a simple parser for a small calculator project, that should be able to parse e.g. the following inputs: ...
David's user avatar
  • 33
1 vote
2 answers
3k views

Proving the grammar S → SS+ | SS∗ | a is unambiguous

Consider the context-free grammar G = ({a, +, ∗}, {S}, {S → SS+ | SS∗ | a}, {S}) and consider the string aa+a* generated by this grammar. Is this grammar unambiguous? I have browsed the Internet and I ...
Charlie's user avatar
  • 127
-1 votes
1 answer
151 views

Lexical analysis on a series of tokens given regexes

I am to parse through a series of strings with a given token list. I was wondering if my lexical analysis is correct. ...
zzzzz's user avatar
  • 1
0 votes
0 answers
9 views

Text macros(replacements) based on pre-defined rules

I'm writing a web app that requires a component that let's the user input a piece of text thats automatically formatted based on something the client calls "macros". These macros have a very ...
3mpir3vampir3's user avatar
0 votes
2 answers
181 views

How to detect if a CFG can cause the parser ends up looping forever?

For example, the following grammar will never stop deriving a complete sentence: S -> A b A -> a A Some other CFGs can derive a complete sentence, but it ...
Stephen.W's user avatar
  • 111
0 votes
1 answer
20 views

Computing Earley Parsing Steps

I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $\Sigma=\{a,b,c\}$: \begin{align*} Z & \to S\\ S & \to a\,|\,b\,|\,c\,|\...
Ido's user avatar
  • 163
0 votes
1 answer
609 views

Reduce-reduce conflict in SLR vs LALR

I was wondering if I could say any of the following is true. Given a grammar $G$, If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$. ...
Ramasamy Kandasamy's user avatar

1
2 3 4 5
9