# Tag Info

12

One book that I can recommend is D. Grune, C. J. H. Jacobs, Parsing Techniques: a Practical Guide.

9

One of the very first applications of category theory to a subject outside of algebraic geometry was to parsing! The keywords you want to guide your search are "Lambek calculus" and "categorial grammar". In modern terms, Joachim Lambek invented noncommutative linear logic in order to model sentence structure. The basic idea is that you can give basic parts ...

7

Here is a grammar that should meet your specification, though it generates the very simple language $a^+(b+c)$. (A simpler grammar has been added below) $S \rightarrow ab \mid aBb \mid ac \mid aCc$ $B \rightarrow a \mid aB \mid aBB$ $C \rightarrow a \mid aC \mid aCC$ How was it built: I started from the grammar $\{S \rightarrow S S \mid a\}$ which is ...

7

In the strictest sense, there is no real difference between syntax errors and semantics errors, at least as far as language theory is concerned: the only salient difference is the complexity of the automaton required to recognize that language, with, e.g. Context-free languages only requiring pushdown automata (PDA) General recursive languages requiring ...

6

Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-02927-1_16 (preprint). For a fixed size alphabet, Sebastian Maneth pointed out to me that $O(n+m)$ is possible for deterministic regular expressions by ...

6

You never need CNF. It has the drawback of changing the grammar structure. But you do need to introduce intermediate non-terminals so that no right-hand-side is longer than 2 (2-form) since RHS length determines the complexity. The best attempt at explaining that intuitively is, if memory serves, a paper by Beau Shiel, "Observations on Context Free Parsing", ...

5

It would appear that (context free) parsing a la Parsec is naturally expressed in terms of the Applicative type class. In turn, this class is described well by so-called strong lax monoidal functors, which are mentioned in this very nice cstheory question and this nice stackoverflow question. More generally, Parsec parsers are monads, that are so well known ...

5

Better late than never. If I understand correctly, Earley is top-down, and will spend time and memory creating Earley items for every production at a given S(i). This means that for natural language, in S(0) we create and check an Earley item for every possible word that starts a sentence, and there are quite a lot of those. But GLR is bottom up, so ...

5

The paper that describes how to build a binarized parse forest in cubic time (mentioned in the post by Angelo Borsotti) is: "SPPF-Style Parsing From Earley Recognizers" by Elizabeth Scott. You can find it here: http://dx.doi.org/10.1016/j.entcs.2008.03.044 In this paper the construction of a shared packed parse forest (SPPF) is described which represents ...

4

Yes, there are lots of automata models for processing XML: I recommend you look into (extensions of) finite tree automata, see e.g. this text book as an intro https://www.worldcat.org/title/foundations-of-xml-processing-the-tree-automata-approach/oclc/692197553 As a basis for building tools check out libvata for a c++ library that handles finite tree ...

4

There is an international agreed notation for describing protocols and format specifications (well actually there are several), which is ASN.1. It is a form of Context_free grammar notation. I used to teach formal notations for networking at one time, but these things have dropped out of the curriculum in favour of security ; which is interesting when a ...

4

The parsing table of a $LL(k)$ grammar grows exponentially in $k$. This is however the worst-case scenario, which is not typical, as Niel pointed out: For an $LL(k)$ grammar $G$, $k$ is the size of the maximal lookahead needed across $L(G)$. But it appears that in practice, the need for a $k$ lookahead is restricted to a small portion to the language, so ...

4

Actually, Chomsky normal form (CNF) is not need to run CYK, only binarization. Binarization is essential to preserve cubic complexity of parsing, though essential only with respect to non-terminals (NT). But then, if you have rules including only 2 non-terminals and some terminals, the CYK algorithm becomes more complex to program and explain. As you say, ...

4

I believe that the following paper explores some of this connection, mostly by using continuations to backtrack when things happen in parsers. But there's definitely more to do here. Modular rollback through control logging: A pair of twin functional pearls Olin Shivers, Aaron Turon, ICFP 2011.

3

If you want to learn about the theory of parsers, I recommend volume 1 of this classic book: Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling, Prentice-Hall (1972).

3

This example grammar is worst case ambiguity, unless I do not understand what you mean by worst case ambiguity. Why do you think it should not be? Try to analyse $a+a+a+a+a$. It's time complexity is $O(n^3)$ with any general CF parser, such as CKY, Earley, GLR, GLL, etc. However, you need only $O(n^2)$ space if you do not keep parse-tree information (though ...

3

How can inherited attributes be simulated with synthesized ones: an example. The way of doing it is to postpone the evaluation of any attribute that uses directly or indirectly an inherited attribute, by abstracting it into a function that takes the inherited attribute as argument. There may be several such arguments. Here is a fragment of a simple example,...

2

Your question is unclear. When you write "parse", do you actually mean to produce a parse structure (one, or all possible ones). How do you define it ? For example, some grammars have a parse tree that differs from the derivation tree. Or did you mean that the language must be fasted to recognize? Regular grammars give you languages that are recognized in ...

2

I am not sure if I get your question right, but this sounds a bit like an extension to Tree Substitution Grammars or Tree Adjoining Grammars (https://en.wikipedia.org/wiki/Tree_adjoining_grammar) I think a string with concatenation points can be interpreted as a tree with replacable nodes. The concatenation replaces the node and the tree is afterwards ...

2

It is hard to say. The boundary between "syntactic errors" and "static semantic errors" can be really blurred. One appropriate example would be Curry-style (extrinsic typing) and Church-style (intrinsic typing) variants of the same programming language, say System F. Failing to include type annotations in the Church-style variant of the language would be a ...

2

I ended up getting a hint on how to accomplish this by reading the leo semantics post from Jeffrey Kegler's deprecated Marpa algorithm page. https://metacpan.org/pod/release/JKEGL/Marpa-PP-0.005_006/pod/Advanced/Algorithm.pod#Leo-Semantics:-Indirect-and-Lazy Snippit that really helped: Leo Semantics: Indirect and Lazy Leo's hints about semantic ...

2

The partial case is presented here: Balancing Straight-Line Programs for Strings and Trees. I'm not sure, that the problem can be solved in the general case.

2

PEGs are unambiguous exactly because at each choice point, i.e, alternatives of a grammar rule, you can choose one and never change it. Context-free grammars, or to be more precise general parsing algorithms like Early or GLR, explore all the alternatives which can lead to ambiguity. We have to also distinguish between ambiguity and non-determinism. PEGs ...

2

So, I'm actually going to reply to your edits first, then come back to your original question. re: Edit 1 In your first edit, you express some confusion over what a parse emitted by an Earley parser is; to explain that I'll jump into a quick refresher on the difference between parsers for deterministic context-free grammars (such as LR parsers) and an ...

2

... is not valid since we have "left recursion" (a variable that calls itself). That's not what a left recursion is. That's simply recursion. Direct left recursion is when a rule $A \to A\alpha$ exists for arbitrary $\alpha$. Indirect left recursion exists when there's a rule $A \to^* A\alpha$ for arbitrary $\alpha$. Note the star, implying possibly many ...

1

Regarding your second question about succinctness, there is a nonrecursive tradeoff in grammar size when moving from general cfgs to unambiguous cfgs. See here: Erik Meineche Schmidt, Thomas G. Szymanski: Succinctness of Descriptions of Unambiguous Context-Free Languages. SIAM J. Comput. 6(3): 547-553 (1977) EDIT (16/3/2019): answering to the comment, by ...

1

While the Parsing Techniques is a great book and I have read some parts several time, it has its focus on LR parsing which won't be interesting for you. In your particular case, you are looking at PEGs which are sort of top-down recursive descent parsing with backtracking based on the order of alternatives. I would like to suggest you to look at parser ...

1

If you don't mind the language difference, Chapter 8 of Higher Order Perl is all about parsing, and in particular builds up a recursive descent parser using parser combinators. It's accessible (if you're not afraid of Perl) and available to read for free if you like. It helped spark my interest in parsing techniques a number of years back.

1

Have you considered converting this into a semantic problem? Instead of grammar rules for all permutations of nonterminals { A, B, C }, simply have one rule to recognize (A | B | C)^3 together with special internal code that makes sure only one of each is recognized, otherwise it declares an error. I would insert an empty production before the above clause,...

1

I'd like to echo the answers above by suggesting you read this paper: http://dx.doi.org/10.1016/j.entcs.2008.03.044 I would like to qualify though by saying that I have implemented the algorithm in this paper and I believe there is an error. In particular, the first sentence of the second paragraph of section 4. The predecessor labels that you make for ...

Only top voted, non community-wiki answers of a minimum length are eligible