Hot answers tagged

65

I have done a lot of research these past few days, to understand better why these separate technologies exist, and what their strengths and weaknesses are. Some of the already-existing answers hinted at some of their differences, but they did not give the complete picture, and seemed to be somewhat opinionated, which is why this answer was written. This ...


48

A parser that returns a (partial) result before the whole input has been consumed is called an incremental parser. Incremental parsing can be difficult if there are local ambiguities in a grammar that are only decided later in the input. Another difficulty is feigning those parts of the parse tree that haven't been reached yet. A parser that returns a ...


47

The short answer is that you use stacks. This is a good example, but I'll apply it to an AST. FYI, this is Edsger Dijkstra's Shunting-Yard Algorithm. In this case, I will use an operator stack and an expression stack. Since numbers are considered expressions in most languages, I'll use the expression stack to store them. class ExprNode: char c ...


40

Usually comments are scanned (and discarded) as part of the tokenization process, but before parsing. A comment works like a token separator even in the absence of whitespace around it. As you point out, the C specification explicitly states that comments are replaced by a single space. It is just specification-lingo though, since a real-world parser will ...


39

I was mistaken, there is a set of "Xtos" functions, they are all just named to_string. Each to_string is overloaded to take a different basic type, i.e.: std::string to_string(float f); std::string to_string(int f); ... See here for more info.


39

The reason is simple: At the time of the first graphical browsers, NCSA Mosiac and later Netscape Navigator, almost all HTML was written by hand. The browser authors (Netscape was built by ex-Mosaic folks) recognized quickly that refusing to render incorrect HTML would be held against them by the users, and voila!


39

From The Digital Antiquarian's article on "The Hobbit": Megler [1] recruited a partner to work with her on the game, Philip Mitchell [2], a fellow senior with whom she had already worked on a number of group projects and whom she knew to be both easy to get on with and a skilled programmer. Milgrom [3] himself added a third member to the team specifically ...


35

Because making best guesses is the right thing to do, from a browser-maker's perspective. Consider the situation: ideally, the HTML you receive is completely correct and to spec. That's great. But the interesting part is what happens when the HTML is not correct; since we're dealing with input from a source that we have no influence on, really, we have to be ...


34

AFAIK, GCC use hand-written parsers in particular to improve syntactic error diagnostics (i.e. giving human meaningful messages on syntax errors). Parsing theory (and the parsing generators descending from it) is mostly about recognizing and parsing a correct input phrase. But we expect from compilers that they give a meaningful error message (and that they ...


33

The critical difference between the two approaches is, that the one he considers to be the only correct way is imperative and yours is declarative. Your approach explicitly declares rules, i.e. the rules of the grammar are (almost) directly encoded in your code, and the parser library automatically transforms raw input into parsed output, while taking care ...


32

A tokenizer is just a parser optimization. It's perfectly possible to implement a parser without a tokenizer. A tokenizer (or lexer, or scanner) chops the input into a list of tokens. Some parts of the string (comments, whitespace) are usually ignored. Each token has a type (the meaning of this string in the language) and a value (the string that makes up ...


27

RAII is not automatically the same thing, but it has the same effect. It provides an easy answer to the question "how do you know when this cannot be accessed any more?" by using scope to cover the area when a particular resource is being used. You might want to consider the similar problem "how can I know my program will not suffer a type error at runtime?"...


23

Take this (contrived) example: void* resource1; void* resource2; while(true){ int input = getInputFromUser(); switch(input){ case 1: resource1 = malloc(500); break; case 2: resource2 = resource1; break; case 3: useResource(resource1); useResource(resource2); break; } } When should free be called? before malloc and ...


20

A parse tree is also known as a concrete syntax tree. Basically, the abstract tree has less information than the concrete tree. The concrete tree contains each element in the language, whereas the abstract tree has thrown away the uninteresting pieces. For example the expression: (2 + 5) * 8 The concrete looks like this ( 2 + 5 ) * 8 | \ | / | | |...


20

Regex can parse any regular language, and cannot parse fancy things like recursive grammars. But CSV seems to be pretty regular, so parseable with a regex. Let's work from definition: allowed are sequence, choice form alternatives (|), and repetition (Kleene star, the *). An unquoted value is regular: [^,]* # any char but comma A quoted value is regular: "...


20

Nice in theory, terrible in practice By CSV I'm going to assume you mean the convention as described in RFC 4180. While matching basic CSV data is trivial: "data", "more data" Note: BTW, it's a lot more efficient to use a .split('/n').split('"') function for very simple and well-structured data like this. Regular Expressions work as a NDFSM (Non-...


19

There is a significant difference between how an AST is typically depicted in test (a tree with numbers/variables at the leaf nodes and symbols at interior nodes) and how it is actually implemented. The typical implementation of an AST (in an OO language) makes heavy use of polymorphism. The nodes in the AST are typically implemented with a variety of ...


19

A rule R is left-recursive if, in order to find out whether R matches, you first have to find out whether R matches. This happens when R appears, directly or indirectly, as the first term in some production of itself. Imagine a toy version of the grammar for mathematical expressions, with only addition and multiplication to avoid distraction: Expression ::=...


19

This topic is very complex. You can google for parser algorithms and you'll get plenty of detailed material. In general: The fewer ambiguities must be resolved, the faster the parsing process. The more tokens have to be considered before a decision can be made, the more complex it gets. For example: When a JS parser sees the function keyword in this code: ...


18

What you need is a true parser. Regular expressions handle lexing, not parsing. That is, they identify tokens within your input stream. Parsing is the context of the tokens, I.E. who goes where and in what order. The classic parsing tool is yacc/bison. The classic lexer is lex/flex. Since php allows for integrating C code, you can use flex and bison to ...


18

I recommend using the Lemon parser generator for parsing. Like Bison, it produces a parser in C. However, its grammar is less error-prone, the parsing interface is reentrant without global variables, and works by you giving tokens to the parser (instead of the parser calling you back to get tokens). You don't really need a lexer generator (e.g. lex). It's ...


17

They usually aren't. They are removed by the lexer, when source code is transformed from characters to tokens. Then, the parser will get tokens and build an AST. When the parser does its job, comment are already gone, so they don't have to appear in the grammar.


17

HTML authors and authoring tools produce crappy markup. Browsers do their best with it for competitive reasons: a browsers that fails to render most of web pages in any reasonable way will be rejected by users, who won’t care the least about whose fault it is. It’s rather different from what programming language implementations do. Compilers and ...


16

GCC switched to hand-written parsing because error messages are more meaningful when using recursive descent techniques, as I explained here. Also, C++ is becoming such a (syntactically) complex language to parse that using parser generators is not worthwhile for it. At last, the bulk of the work of a real compiler is not parsing, it is optimizing. GCC ...


16

You'd usually expect most syntax errors to come from the parser, not the lexer. The lexer would generate an error if (and mostly only if) there's something in the input that can't be tokenized. In many languages, however, almost any sequence of characters can be turned into tokens of some sort, so errors here are fairly unusual. The parser will generate an ...


15

Under parsing we understand most often analysis of context free languages. A context free language is more powerful than a regular one, hence the parser can (most often) do the job of the lexical analyser right away. But, this is a) quite unnatural b) often inefficient. For a), if I think about how for example an if expression looks, I think IF expr THEN ...


14

Let me admit frankly, building parser is a tedious job and comes close to compiler technology but building one would turn out to be a good adventure. And a parser comes with interpreter. So you got to build both. A quick introduction to parser and interpreters This is not too technical. So experts don't fret at me. When you feed some input into a terminal,...


14

You could use something like YAML. Here is a link to an example: http://www.yaml.org/start.html --- !clarkevans.com/^invoice invoice: 34843 date : 2001-01-23 bill-to: &id001 given : Chris family : Dumars address: lines: | 458 Walkman Dr. Suite #292 city : Royal Oak state : MI ...


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