Questions tagged [parsing]

Parsing is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.

27 questions
Filter by
Sorted by
Tagged with
28 views

Parsing a nested inference rule syntax

Consider this expression. $$\dfrac{\dfrac{\dfrac{\dfrac{}{\textsf{zero nat}}}{\textsf{succ(zero) nat}}}{\textsf{succ(succ(zero)) nat}}}{\textsf{succ(succ(succ(zero))) nat}}$$ I see several ...
17 views

How to evaluate this type of arithmetic syntax tree in general?

I have a syntax tree, like this: Tree I can evaluate any syntax tree easily when there are no terms, with a similar code (I wrote a simpler pseudo code): ...
62 views

An explicit algorithm to test whether a string of symbols is or is not well-formed in this language.

Consider the set of five symbols, $\{ (, ), p, ', *\}$. A variable is defined as $p$ followed by zero or more $'$s. A wff is inductively defined as follows: $1$. Every variable is a wff. $2$. If $x$ ...
27 views

Unique parsing means?

After searching this site for the key words "unique parsing" "parsing" and "unique parsing lemma," and finding nothing really applicable to me (or as far as I could tell),...
31 views

Is every sentential form also a right-sentential form?

Ullman's Introduction to Automata, Languages and Computing (1979) says 10.6 LR(0) GRAMMARS ... A right-sentential form is a sentential form that can be derived by a rightmost derivation. Is every ...
12 views

How to characterize the set of grammars which recursive descent parsers can apply to?

How would you characterize the set of grammars which recursive descent parsers can apply to: no left recursion (both immediate and not) left factored no cycle no epsilon rule ... Predicative ...
20 views

Are there subset/superset relations between the languages which can be parsed by these different kinds of parsers?

I have been confused by the different types of parsers listed in https://en.wikipedia.org/wiki/Parsing#Types_of_parsers and https://en.wikipedia.org/wiki/Template:Parsers Are there some top-down and ...
30 views

Is a CFL parser counted as an automaton, and even a PDA?

Is a CFL parser counted as an automaton? Even more, is a CFL parser counted as a PDA? I found that a CFL parser is defined directly based on a CFG, while the concepts of CFG and PDA are defined ...
26 views

Correctness properties, judgments and rules [closed]

Definition: sD means $s$ is a digit, i.e. $s$ is one of $0,1,\dots,9$. k Nat means $k\in\bf N$. Proposition: If sD <-> k Nat then sD and k Nat. I don't really understand what I have to prove. ...
19 views

Proving a Formal Grammar Parses a String.

In summary, I am interested to know (at a high level) what a proof would look like, and what I would need to do in developing a grammar, to "prove" that the grammar matches some patterns I have in ...
114 views

Can first-order logic be recognized by a pushdown automaton?

I have the belief that first-order logic cannot be recognized by a pushdown automaton because the automaton will have no way to keep track of the variables that are currently in scope. More precisely, ...
1k views

Is First Order Logic Syntax Context Free?

If I were to build a first order logic parser could I do it using a context free parser generator (like bison)? I found some articles where First Order Logic Syntax is described with EBNF notation, ...
47 views

This is a ll(1) of logic propositions?

I have this is grammar : F = F and F F = F or F F = F => F F = F <=> F F = not F F = (F) D = a but this grammar has a ambiguity , i'm Stripped a ...
83 views

Interpreting “pairwise”

I have the following exercise. Can four lines in space (not necessarily passing through the same point) be pairwise perpendicular? Does it mean (given 4 lines $a$, $b$, $c$, and $d$): $a\perp b$; ...
117 views

I am confused about how epsilon works in parsing tables (or my book is wrong)?

So I'm reading my lecture notes and something really confuses me: Shouldn't the [Y,+] entry produce an error as there is no possible way you can get the string '+' from Y? Why then does it say it ...
555 views

Evaluating an arithmetic abstract syntax tree [closed]

This might be very simplistic for this forum (apologies, if so). How does one evaluate the tree below. I am not looking for a solution, just assistance in how to evaluate it: I assume I start at the ...
251 views

Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
76 views

Create a formula for order of parenthesis

I am stumped at creating a formula (for a coded math problem evaluator) that finds what is within the parenthesis. It gets tricky when you have () within ...
126 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
20 views

Relationships between $\operatorname{LL}(k)$, $\operatorname{LR}(k)$ language sets

I'm trying to establish (through constructing a Hasse diagram) the subset relationship between the classes of languages that can be parsed by $\operatorname{LL}(k)$ and $\operatorname{LR}(k)$ parsers. ...
64 views