Questions tagged [parsing]
Analyzing (un)structured data to convert it into a structured, normalized format.
294
questions
115
votes
4
answers
22k
views
When to use a Parser Combinator? When to use a Parser Generator?
I've taken a deep dive into the world of parsers recently, wanting to create my own programming language.
However, I found out that there exist two somewhat different approaches of writing parsers: ...
- 4,619
103
votes
12
answers
36k
views
Should I use a parser generator or should I roll my own custom lexer and parser code?
What specific advantages and disadvantages of each way to working on a programming language grammar?
Why/When should I roll my own? Why/When should I use a generator?
- 10.8k
51
votes
4
answers
74k
views
How exactly is an Abstract Syntax Tree created?
I think I understand the goal of an AST, and I've built a couple of tree structures before, but never an AST. I'm mostly confused because the nodes are text and not number, so I can't think of a nice ...
- 711
43
votes
1
answer
44k
views
C++11 includes std::stoi, why not std::itos?
I noticed to my glee that C++11 has a std::sto@ family of functions for easily unpacking ints/floats/longs whatever from strings. I'm surprised however, that the opposite isn't implemented. Why didn't ...
- 11.6k
41
votes
2
answers
10k
views
Do modern languages still use parser generators?
I was researching about the gcc compiler suite on wikipedia here, when this came up:
GCC started out using LALR parsers generated with Bison, but gradually switched to hand-written recursive-...
- 561
38
votes
7
answers
4k
views
Why was strict parsing not chosen for HTML?
I have often wondered why strict parsing was not chosen when creating HTML. For most of the Internet history, browsers have accepted any kind of markup and tried their best to parse it. The process ...
- 703
34
votes
5
answers
9k
views
How are comments usually parsed?
How are comments generally treated in programming languages and markup? I am writing a parser for some custom markup language and want to follow the principle of least surprise, so I'm trying to ...
- 1,858
30
votes
1
answer
2k
views
The Inglish parser (for The Hobbit 1982)
Was fascinated to read about the text adventure game The Hobbit which featured an incredibly robust parser called "Inglish":
...Inglish allowed one to type advanced sentences such as "ask Gandalf ...
- 623
27
votes
8
answers
5k
views
Is it possible to statically predict when to deallocate memory---from source code only?
Memory (and resource locks) are returned to the OS at deterministic points during a program's execution. The control flow of a program by itself is enough to know where, for sure, a given resource can ...
- 575
27
votes
5
answers
46k
views
Can the csv format be defined by a regex?
A colleague and I have recently argued over whether a pure regex is capable of fully encapsulating the csv format, such that it is capable of parsing all files with any given escape char, quote char, ...
- 3,566
27
votes
5
answers
3k
views
Name for this type of parser, OR why it doesn't exist
Conventional parsers consume their entire input and produce a single parse tree. I'm looking for one that consumes a continuous stream and produces a parse forest [edit: see discussion in comments ...
- 2,576
26
votes
3
answers
25k
views
Implementing the Visitor Pattern for an Abstract Syntax Tree
I'm in the process of creating my own programming language, which I do for learning purposes. I already wrote the lexer and a recursive descent parser for a subset of my language (I currently support ...
- 8,691
25
votes
7
answers
3k
views
What are the arguments against parsing the Cthulhu way?
I have been assigned the task of implementing a Domain Specific Language for a tool that may become quite important for the company. The language is simple but not trivial, it already allows nested ...
- 261
25
votes
3
answers
3k
views
In which process does syntax error occur? (tokenizing or parsing)
I'm trying to understand compilation and interpretation, step by step figuring out a total image. So I came up to a question while reading http://www.cs.man.ac.uk/~pjj/farrell/comp3.html this article
...
- 469
23
votes
5
answers
8k
views
Are separate parsing and lexing passes good practice with parser combinators?
When I began to use parser combinators my first reaction was a sense of liberation from what felt like an artificial distinction between parsing and lexing. All of a sudden everything was just ...
- 331
22
votes
12
answers
11k
views
How to write a command interpreter/parser?
Problem: Run commands in the form of a string.
command example:
/user/files/ list all;
equivalent to:
/user/files/ ls -la;
another one:
post tw fb "HOW DO YOU STOP THE TICKLE MONSTER?;"
equivalent ...
- 413
21
votes
3
answers
16k
views
Do compilers utilize multithreading for faster compile times?
If I remember my compilers course correctly, the typical compiler has the following simplified outline:
A lexical analyzer scans (or calls some scanning function on) the source code character-by-...
- 1,359
19
votes
4
answers
2k
views
Generic rule parser for RPG board game rules - how to do it?
I want to build a generic rule parser for pen and paper style RPG systems. A rule can involve usually 1 to N entities 1 to N roles of a dice and calculating values based on multiple attributes of an ...
- 471
18
votes
3
answers
12k
views
What issues tend to arise when working with HL7 messages?
I'm testing a product for health care businesses, and we're working with HL7 messages. I saw people groaning on another question about the issues with HL7 but not mentioning specifics. Can someone ...
- 5,329
16
votes
5
answers
6k
views
Coming up with tokens for a lexer
I'm writing a parser for a markup language that I have created (writing in python, but that's not really relevant to this question -- in fact if this seems like a bad idea, I'd love a suggestion for a ...
- 1,919
15
votes
5
answers
11k
views
unit tests for a csv parser
What tests should I use to unit test a csv parser?
I have a simple csv parser in C#, and I want to be sure I have good unit test coverage of all the common (and uncommon) edge cases. What tests ...
- 1,857
15
votes
3
answers
3k
views
How would you test a lexer?
I'm wondering how to effectively test a lexer (tokenizer).
The number of combinations of tokens in a source file can be huge, and the only way I've found is to make a batch of representative source ...
- 413
15
votes
6
answers
12k
views
What is the simplest human readable configuration file format? [closed]
Current configuration file is as follows:
mainwindow.title = 'test'
mainwindow.position.x = 100
mainwindow.position.y = 200
mainwindow.button.label = 'apply'
mainwindow.button.size.x = 100
...
- 303
14
votes
2
answers
7k
views
In layman's terms, what is left recursion?
According to one page on code.google.com, "left recursion" is defined as follows:
Left recursion just refers to any recursive nonterminal that, when it produces a sentential form containing ...
- 3,125
14
votes
2
answers
4k
views
What's the simplest example out there to explain the difference between Parse Trees and Abstract Syntax Trees?
To my understanding, a parser creates a parse tree, and then discards it thereafter. However, it can also pop out an abstract syntax tree, which the compiler supposedly makes use of.
I'm under the ...
- 143
14
votes
2
answers
2k
views
What does scannerless parsing have to do with the "Dangling Else Problem"?
I do not understand this sentence from the Wikipedia article on the Dangling Else problem:
[The Dangling Else problem] is a problem that often comes up in compiler construction, especially ...
user39685
14
votes
1
answer
6k
views
Why did GCC switch from Bison to a recursive descent parser for C++ and C?
Was there a language change that required it or some practical reason why Bison was no longer appropriate or optimal?
I saw on wikipedia that they switched, referring to the GCC 3.4 and GCC 4.1 ...
- 473
14
votes
3
answers
31k
views
Generic file parser design in Java using the Strategy pattern
I am working on a product in which the responsibility of one of the modules is to parse XML files and dump the required content in a database. Even though the present requirement is only to parse XML ...
- 1,012
13
votes
3
answers
6k
views
How should I specify a grammar for a parser?
I have been programming for many years, but one task that still takes me inordinately long is to specify a grammar for a parser, and even after this excessive effort, I'm never sure that the grammar I'...
13
votes
2
answers
1k
views
language with two binary operators of same precedence, left-associative & right-associative
Are there any programming (or scripting) language (or some domain specific language) having two binary operators opl and opr of same precedence with opl being left-associative and opr being right-...
- 32.3k
13
votes
5
answers
545
views
How can I best manage making open source code releases from my company's confidential research code?
My company (let's call them Acme Technology) has a library of approximately one thousand source files that originally came from its Acme Labs research group, incubated in a development group for a ...
- 4,958
12
votes
6
answers
7k
views
How to Unit-Test a parser of a file?
I'm implementing a metadata parser of image files from all formats. I want to write tests for it. One trivial way to do so is to have test image files of all formats as a resources for the tests, and ...
- 223
12
votes
2
answers
2k
views
Persisting natural language processing parsed data
I've recently started experimenting with natural language processing (NLP) using Stanford's CoreNLP, and I'm wondering what are some of the standard ways to store NLP parsed data for something like a ...
user25791
11
votes
3
answers
10k
views
Is there a more modern program than lex or yacc, which does not require JVM? [closed]
Is there a "modern" bison and flex equivalent which does not require the JVM or .NET or similar "heavy" runtimes?
By modern, I mean for example Antlr and another one in Java I saw but forgot the name ...
- 271
11
votes
7
answers
7k
views
Techniques for parsing XML
I've always found XML somewhat cumbersome to process. I'm not talking about implementing an XML parser: I'm talking about using an existing stream-based parser, like a SAX parser, which processes the ...
- 2,475
11
votes
2
answers
5k
views
Algorithm for formating SQL code
I need a tool (for in house usage) that will format SQL code (SQL Server/MySQL).
There are various 3rd party tools and online web sites that do it but no exactly how I need it.
So I want to write my ...
- 111
10
votes
5
answers
45k
views
Getting data from a webpage in a stable and efficient way
Recently I've learned that using a regex to parse the HTML of a website to get the data you need isn't the best course of action.
So my question is simple: What then, is the best / most efficient and ...
- 203
10
votes
4
answers
2k
views
Writing a Compiler Compiler - Insight on Use and Features
This is part of a series of questions which focuses on the sister project to the Abstraction Project, which aims to abstract the concepts used in language design in the form of a framework. The ...
10
votes
1
answer
1k
views
Does a GPL Bison grammar infect my application?
I am thinking about using a GPL Bison grammar for my own compiler.
Will the grammar "infect" my parser such that it needs to be open source?
The grammar - in terms of - the input of bison is GPL.
- 201
9
votes
6
answers
8k
views
Best way to parse a file
I'm trying to find a better solution for making a parser to some of the famous file formats out there such as: EDIFACT and TRADACOMS.
If you aren't familiar with these standards then check out this ...
- 6,548
9
votes
1
answer
657
views
What makes some things easier to parse than others?
I was just reading the Wikipedia page for WebAssembly and it says: “WebAssembly is… designed to be faster to parse than JavaScript” , which got me thinking, what makes a certain language or data ...
- 228
9
votes
4
answers
413
views
How should I implement a command processing application?
I want to make a simple, proof-of-concept application (REPL) that takes a number and then processes commands on that number.
Example:
I start with 1. Then I write "add 2", it gives me 3. Then I ...
- 283
9
votes
2
answers
6k
views
Language parsing to find important words
I'm looking for some input and theory on how to approach a lexical topic.
Let's say I have a collection of strings, which may just be one sentence or potentially multiple sentences. I'd like to ...
- 191
9
votes
3
answers
1k
views
What the correct algorithm to invert italics in a mixed text?
The question motivations was depicted in the section below.
There are many ways to make text italic,
so, perhaps, there are more than one good
"swap italics algorithm".
The problem reveals some ...
- 747
8
votes
5
answers
4k
views
What is the responsibility or benefit of a Tokenizer?
Suppose I had a grammar like:
object
{ members }
members
pair
pair
string : value
value
number
string
string
" chars "
chars
char
char chars
number
digit
...
- 326
8
votes
4
answers
1k
views
How are comments expressed in programming language grammars?
I'm learning how to build parsers using grammars, but I got stuck trying to express comments, because they can appear almost anywhere.
This indicates that comments can be stripped from the token ...
user39685
8
votes
4
answers
2k
views
Using a "dead man's switch" to manage time-sensitive code
In our software environment, we often run a/b tests, as is probably good practice. However, our environment is set up such that, in very short order, the code starts to become very crufty with dead ...
- 221
8
votes
3
answers
3k
views
What is a real-world use case of using a Chomsky Type-I (context-sensitive) grammar
I have been having some fun lately exploring the development of language parsers in the context of how they fit into the Chomsky Hierarchy.
What is a good real-world (ie not theoretical) example of a ...
- 5,715
8
votes
3
answers
2k
views
Clarification about Grammars , Lexers and Parsers
Background info (May Skip): I am working on a task we have been set at uni in which we have to design a grammar for a DSL we have been provided with. The grammar must be in BNF or EBNF. As well as ...
- 191
8
votes
4
answers
5k
views
When to use ANTLR and when to use a parsing library
I've always wanted to learn how to write a compiler - I've decided to use ANTLR, and am currently reading through the book (its very good by the way)
I'm pretty new to this, so go easy, but the jist ...
- 2,445