Hot answers tagged

109 votes
Accepted

When to use a Parser Combinator? When to use a Parser Generator?

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 ...
Qqwy's user avatar
  • 4,789
20 votes
Accepted

What is the procedure that is followed when writing a lexer based upon a grammar?

Lexers are just simple parsers that are used as a performance optimisation for the main parser. If we have a lexer, the lexer and the parser work together to describe the complete language. Parsers ...
amon's user avatar
  • 134k
16 votes
Accepted

How would you test a lexer?

Your grammar probably has some rules for each token on how it can be produced (for example, that a { signifies a BLOCK_START token, or that a string-literal token is delimited by '"' characters). ...
Bart van Ingen Schenau's user avatar
16 votes

How would you test a lexer?

If you're writing the lexer yourself, this seems like an ideal case for test-driven development. While “the number of combinations of tokens in a source file can be huge,” the number of branches in ...
Arseni Mourzenko's user avatar
13 votes
Accepted

What should be the datatype of the tokens a lexer returns to its parser?

Generally, if you're processing a language though lexing and parsing, you've got a definition of your lexical tokens, e.g.: NUMBER ::= [0-9]+ ID ::= [a-Z]+, except for keywords IF ::= 'if' ...
Joshua Taylor's user avatar
11 votes
Accepted

Should my lexer allow what is obviously a syntax error?

Your lexer is never going to be able to diagnose all syntax errors unless you make it as powerful as the parser itself. This would be a large and totally unnecessary amount of work, and the only ...
Kilian Foth's user avatar
11 votes

When to use a Parser Combinator? When to use a Parser Generator?

For input that is guaranteed to be free of syntax errors, or where an overall pass/fail on syntactic correctness is okay, parser combinators are much simpler to work with, especially in functional ...
Karl Bielefeldt's user avatar
10 votes

In which way should I structure a compiler/Interpeter?

Looking at your description of the problems you are encountering and at the architecture and design you are describing in general (i.e. without even considering the fact that it is a compiler), your ...
Jörg W Mittag's user avatar
8 votes

When to use a Parser Combinator? When to use a Parser Generator?

Sam Harwell, one of the maintainers of the ANTLR parser generator, recently wrote: I found [combinators] do not meet my needs: ANTLR provides me with tools for managing things like ...
Mason Wheeler's user avatar
8 votes

What should be the datatype of the tokens a lexer returns to its parser?

As said in the title, which data type should a lexer return/give the parser? "Token", obviously. A lexer produces a stream of tokens, so it should return a stream of tokens. He mentioned Flex, a ...
Eric Lippert's user avatar
  • 46.1k
8 votes
Accepted

How should a lexer deal with multi-line statements(eg. Functions definitions, Control-Flow statements)?

As you've already conjectured, this is not the lexer's job. It doesn't trade in terms of statements, declarations and definitions but in much more low-level entities called tokens. For example, for ...
5gon12eder's user avatar
  • 6,986
7 votes

How would you test a lexer?

One alternative that others aren't mentioning, is to use a test generative approach—like QuickCheck from Haskell—to generate the edge cases from the grammar you've defined. Now, once they're generated,...
A T's user avatar
  • 727
6 votes

How do I create my own Objective-C to Swift converter?

This is a pretty big task. But then again, so are most things worth doing in programming. We start by breaking it down into smaller and smaller tasks until we get them down to the level of a problem ...
Mason Wheeler's user avatar
6 votes
Accepted

Is there any need to have an evaluation stage for a lexer to properly work?

why would one not design their lexer in such a way, so that the scanner goes ahead and classifies the lexemes it creates, instead of passing it to separate stage? We don't have to take these stages ...
Erik Eidt's user avatar
  • 33.7k
5 votes

When to use a Parser Combinator? When to use a Parser Generator?

As Karl mentions, parser generators tend to have better error reporting. In addition: they tend to be faster, since the generated code can be specialized for the syntax and generate jump tables for ...
Telastyn's user avatar
  • 109k
5 votes
Accepted

Is it appropite for a tokenizer to use regex to gather tokens?

Regexs work great for lexing / tokenization. TL;DR Using regular expressions to tokenize is entirely appropriate. The default approach, really. As for efficiency, regexs traditionally map directly ...
Jonathan Eunice's user avatar
4 votes

Is it appropite for a tokenizer to use regex to gather tokens?

Using regular expressions to tokenize is a classic approach. More modern approaches to parsing would be using a PEG-based ("parsing expression grammar") parser. Either way works, but having the ...
Vatine's user avatar
  • 4,259
4 votes
Accepted

Do lexers have to go word by word or can they go line by line

If you have a grammar, then that should be your guide.  Going line-by-line is reasonable in a grammar and would simply include newlines in the grammar as starting or finishing syntactic constructs (...
Erik Eidt's user avatar
  • 33.7k
4 votes
Accepted

Is it a good idea to let keywords have different lexical rules from names of types, variables, functions, etc?

Distinguishing keywords/operators from user-defined names is not strictly necessary. Scannerless parsers can do just fine regardless. For example, it would be feasible to define a language where the ...
amon's user avatar
  • 134k
3 votes

Do any programming languages let you use other languages without restriction within them?

Not really. Language interop is a difficult problem, and language embedding even more so. Many languages have nontrivial syntax constructs that cannot be easily parsed by a general purpose parser. ...
amon's user avatar
  • 134k
3 votes
Accepted

How do parsers search for token patterns?

It looks like it was easy to implement when I look at it, but if I should invent an algorithm for it, I couldn't. Thankfully some people already have :) https://en.wikipedia.org/wiki/Backus%E2%80%...
Pod's user avatar
  • 734
3 votes

What should be the datatype of the tokens a lexer returns to its parser?

Generally, you return a small structure which has a number signifying the token (or enum value for ease of use) and an optional value (string, or possibly generic/templated value). Another approach ...
Telastyn's user avatar
  • 109k
2 votes

Why implement a lexer as a 2d array and a giant switch?

Having worked through the Dragon Book before, the principle reason for having table driven levers and parsers is so that you can use regular expressions to generate the lexer and BNF to generate the ...
Robert Baron's user avatar
  • 1,132
2 votes
Accepted

Is it possible to parse my grammar with multi-line productions without backtracking?

Strictly speaking, the only way to prevent any backtracking whatsoever while supporting multi-line statements is to either have an explicit "the upcoming newline is not the end of a rule" character, ...
Ixrec's user avatar
  • 27.7k
2 votes
Accepted

How to create simulator for distributed algorithms written in simple language

Why would you use lowest-possible level language, C, for an involved task like this? Or, rather, several tasks? If I needed results quickly and painlessly, I'd take a purpose-built tool, like Erlang ...
9000's user avatar
  • 24.2k
2 votes

Should my lexer allow what is obviously a syntax error?

First a caveat: It very much depends on which subset of HTML. HTML5 does not really have the concept of errors at all. Basically any sequence of characters is valid and have a defined parse. I will ...
JacquesB's user avatar
  • 58.7k
2 votes
Accepted

How does a lexer handle template strings?

Two typical solutions: give up on using a separate lexer. This is easy and efficient with top-down parsing approaches such as recursive descent, PEG, or parser combinators. Such an approach makes it ...
amon's user avatar
  • 134k
2 votes
Accepted

How is it possible to store the AST nodes location in the source code?

Yes, you have described the standard approach. Creating a raw text node type which has a line number, and then having others inherit from that might be attractive. Error messages will typically want ...
J_H's user avatar
  • 6,540
2 votes

How Should Lexers Be Stateful?

It depends on the kind of languages and it depends on whether you see statefulness on the input or the output side of the lexer. On the input side, lexers are often stateful: If you parse a string ...
Christophe's user avatar
  • 76.8k

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