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
2 answers
37 views

Parse Tree simple example

Consider the grammar G: S ➝ A | B A ➝ aB | b | c B ➝ bA | a | ε Which of the following strings has two parse trees according to G? ba bb ab none of the choice aa ...
tmhs's user avatar
  • 97
0 votes
0 answers
22 views

Methods to tell the length of data?

What methods are there for telling a computer how long a set of data is? Here are the methods I know of: Directly telling the computer where the data begins and ends, most often with {} or (). Having ...
user avatar
-3 votes
0 answers
12 views

Bluetooth between app and seeed studio xiao nrf52840 [closed]

We are using the app and connecting to a seeed studio xiao nrf52840 microcontroller. We have gotten the app and microcontroller to connect via bluetooth and have the microcontroller sending data ...
Leta's user avatar
  • 1
0 votes
0 answers
22 views

How to use Jflex to generate a lexer properly?

I was told that making lexer from scrath is really hard and that we should use built in libraries. I used an already existing example to build my program. It worked but was full of error partially ...
Oh No's user avatar
  • 11
1 vote
0 answers
30 views

Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit

Background I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
Jerry Ding's user avatar
0 votes
1 answer
32 views

Table driven parser vs Recursive Descent parser

I am currently writing an LL(1) parser. At several places (Engineering a Compiler book, Dragon book, or this discussion), I have seen two ways to go about this, either with a table driven parser (...
Ali Ahmed's user avatar
0 votes
0 answers
58 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
20 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
17 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
71 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
194 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
46 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
71 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
43 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
61 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
138 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
1 answer
62 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
45 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
  • 167
0 votes
1 answer
87 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
  • 167
0 votes
1 answer
57 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
65 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
565 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
  • 151
0 votes
1 answer
98 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
40 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
518 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
139 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
94 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
115 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
147 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
106 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
60 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
32 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
236 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
30 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
354 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
590 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
263 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
290 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
56 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
420 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
4k 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
2 3 4 5
9