Skip to main content

Questions tagged [parsing]

For questions related to the parsing stage of code compilation or interpretation. Parsing is the process of converting text-based code into the constituent logic.

Filter by
Sorted by
Tagged with
0 votes
1 answer
264 views

From a parsing perspective, which is more efficient? Right-to-left or left-to-right argument parsing?

C (and other languages which allow variable argument lists) process function arguments from right-to-left. Pascal (and other languages with fixed-length argument lists) process function arguments from ...
warren's user avatar
  • 117
2 votes
1 answer
158 views

How is the VHDL operator `<=`, which can be both right-associative (signal assignment) and left-associative (less-than-or-equal), parsed?

One of the most confusing things to me about VHDL is that the <= operator can mean both "less than or equal to" and it can be a signal assignment ...
FlatAssembler's user avatar
14 votes
4 answers
1k views

Why do we need to divide lexing and parsing stages

Why do many typical parsers need to have two stages: tokenization and parsing? This isn't just a helping hand for manually-constructed parsers, as even generation tools do the same. For example, the ...
Aster's user avatar
  • 3,198
24 votes
7 answers
12k views

Why do compilers typically convert code into abstract syntax/parse trees before the final product?

When I started researching parsing and compiling I started with simple mathematical expression parsers. Many of the existing implementations I found have an intermediate step of converting a string ...
CPlus's user avatar
  • 8,261
2 votes
3 answers
922 views

How to support syntax like `a && b = c` for a conditional assignment expression?

I want the expression a && b = c in my language to mean that the value of c is assigned to ...
DannyNiu's user avatar
  • 229
1 vote
1 answer
170 views

Does it make sense to track previous tokens literally in a parser generator? [closed]

As a beginner in parser generators, is it memory intensive or not to retain the set of parsed tokens in a collection? Or do actual parser generators refine what was previously parsed from a structure ...
Hydroper's user avatar
  • 1,007
2 votes
0 answers
154 views

Issue with rules for custom DSL

I am struggle with implementing rules for a custom DSL with significant spaces. The key feature is that it requires spaces to be tracked and re-used. In most languages they are used to split tokens ...
defance's user avatar
  • 129
25 votes
4 answers
3k views

Why don't popular regex engines support complement and intersection?

While regex size blows up when defining a function that take two regexes, and return one regex representing their complement/intersection (see Succinctness of the Complement and Intersection of ...
Marisa Kirisame's user avatar
12 votes
2 answers
597 views

How to tolerate syntax errors in a typed language?

In my tokenizers and parsers, once I find a syntax error (like an unexpected token) I usually throw a fatal exception that finishes parsing of the input source. The downside of how I usually do it is ...
Hydroper's user avatar
  • 1,007
14 votes
1 answer
1k views

What exactly is Pratt parsing used for and how does it work?

I've come across the term “Pratt parsing”. The only thing I know is that it's an algorithm (or a pattern, a technique) used to parse expressions. How does it work? I'd like to see the intuition behind ...
Lazar Ljubenović's user avatar
10 votes
4 answers
2k views

Do parsers typically need access to all tokens?

Do parsers typically operate on the entire array/list of tokens available in memory, or are the tokens often streamed one by one as they are recognized? What influences the decision?
Lazar Ljubenović's user avatar
9 votes
1 answer
687 views

How does Rust parse ambiguous macros?

Rust's macros require them to be delimited by either parentheses, braces, or brackets, such as println!(arg) or foo! { bar, baz }...
Seggan's user avatar
  • 2,673
2 votes
3 answers
266 views

How do different template languages handle parsing?

In template languages, most of the content is written out as-is, with only certain special markers for expression evaluation or flow control. In my attempts to develop a language of this style, I've ...
kouta-kun's user avatar
  • 1,359
6 votes
2 answers
175 views

How to determine the meaning of a polymorphic operator?

Some operators have multiple meanings. For example: - represents the prefix negative, or it can represent the infix ...
Aster's user avatar
  • 3,198
-2 votes
1 answer
201 views

How to provide a sensible error message for `load (load s0, s1), s2` when parsing assembly? [closed]

Suppose somebody completely misunderstands how assembly language works and, instead of writing: load s1, s2 load s0, s1 He writes: ...
FlatAssembler's user avatar
-1 votes
1 answer
295 views

Look behind in parsers [closed]

If Sandwich's AST generator finds that the first token is an identifier, one of two cases can be true: Function call Variable assignment It stores the identifier and checks if the next token is a = ...
The_AH's user avatar
  • 17
17 votes
6 answers
8k views

Does Python's semicolon statement ending feature have any unique use?

Python does not usually use explicit line-ending characters; the parser can almost always figure out where a statement ends from the positioning of newlines. However, Python's syntax allows you to use ...
Ginger's user avatar
  • 2,619
17 votes
2 answers
3k views

How do lexers/parsers distinguish between nested generics and bitshifts?

The lexical grammar of Java has a special case for the the > character. Normally, tokens are formed based on the longest-match rule, so that an input string of <...
kaya3's user avatar
  • 19.1k
7 votes
1 answer
254 views

Techniques for resilient parsing in the face of mismatched brackets?

Suppose you want to build an IDE-grade parser for a language with highly uniform and nestable syntax (e.g. Lisp). Without a lot of "special" constructs like top-level functions, you can't ...
Ken Micklas's user avatar
5 votes
2 answers
2k views

How can the shunting yard algorithm be adapted to handle currying?

The shunting yard algorithm is used to parse infix expressions into a syntax tree, or prefix/postfix notation. Wikipedia provides pseudocode for how to implement it, but notes: This implementation ...
Bbrk24's user avatar
  • 8,937
2 votes
1 answer
222 views

What are the exact requirements of not requiring forward declarations everywhere?

Some languages like C and C++ require defining the names before using them, though the definition could sometimes be only a header specifying something is a struct or function without the body. Some ...
user23013's user avatar
  • 2,390
3 votes
1 answer
141 views

How do I explain to a syntax highlighter to highlight `a` differently in `load s0, a` (where it is a hexadecimal constant) and `regbank a`? [duplicate]

In the syntax highlighter I have implemented in my PicoBlaze Simulator in JavaScript, the assembly code address 0 load s0, 0 load s0, a regbank a is highlighted as ...
FlatAssembler's user avatar
10 votes
2 answers
588 views

What are the advantages of parser combinators?

Motivation There seems to be something popular in the rust community called parser combinators. I temporarily use a traditional recursive descent parser, my syntax is not yet stable, composition means ...
Aster's user avatar
  • 3,198
8 votes
7 answers
1k views

Pros and cons of whitespace or comments being included as tokens

What are the pros and cons of including whitespace and comments as tokens in the tokenizer output? For example: value= 6+ 7 // A comment Would result in these ...
MarcellPerger's user avatar
5 votes
1 answer
141 views

Do let bindings need an assignment operator for disambiguation?

Let's say I want to allow (conservative) let bindings, with optional type ascription. Most imperative languages would put a = or ...
user avatar
5 votes
1 answer
185 views

What sort of "syntax error recovery" is possible for this indentation based language?

I am thinking of how to write the parser/compiler so it works as a VSCode Language Server Extension, so I can have it show syntax errors, do autocomplete, and other things, in VSCode. One thing that I'...
Lance's user avatar
  • 705
9 votes
1 answer
442 views

Parsing `do`-`while`, `while`-`do`-`end` and `do`-`end`

Consider the Lua programming language, which has the following constructs involving the keywords do and end: ...
Luatic's user avatar
  • 330
22 votes
7 answers
8k views

Why do most languages use the same token for `EndIf`, `EndWhile`, `EndFunction` and `EndStructure`?

In my programming language, AEC, I am using keywords EndIf and EndWhile with the same meaning as in SmallBasic, and I am also ...
FlatAssembler's user avatar
11 votes
5 answers
993 views

What are the pros and cons of a compiler with a single-pass parser?

Assume you are tasked with writing a compiler for a language that can be parsed in a single pass, like C, but does not necessarily have to be. What are the pros and cons for doing this? Would you do ...
Gavin D. Howard's user avatar
13 votes
3 answers
2k views

What are the pros and cons of single-pass compilers?

Okay, we all know the standard compiler architecture: a batch program with multiple passes for parsing, optimizing, and generating code. Suppose you wanted to go all Turbo Pascal and implement a ...
Gavin D. Howard's user avatar
4 votes
2 answers
378 views

Does a simple syntax stack based language need a parser?

I have been working on a standard for a simple stack based language for a few weeks now. It has an extremely simple syntax. ...
poggingfish's user avatar
4 votes
1 answer
238 views

Is PicoBlaze assembly language a context-sensitive language?

I know one example of context-sensitivity in programming languages is the so-called typedef problem. Basically, the words can be different types, and that influences how a sentence may be parsed. For ...
FlatAssembler's user avatar
6 votes
2 answers
249 views

How can a compiler's parse errors be tested?

There are fairly straightforward ways to test a compiler's behaviour on valid programs: most obviously, build a suite of programs to run through the compiler, and know what should happen when they run....
Michael Homer's user avatar
  • 12.9k
3 votes
3 answers
209 views

How can I track source spans during parsing and interpretation?

I want to implement error messages that point out where in your source code a parse error or runtime error is. However, when I convert the token stream to my AST, I lose the information about the ...
bigyihsuan's user avatar
  • 1,821
11 votes
2 answers
481 views

What are some caveats to be careful about when implementing the `?:` (ternary conditional) operator?

Thus far, I see two things that can go wrong when implementing the ?: (ternary conditional) operator: PHP famously incorrectly implemented the ...
FlatAssembler's user avatar
7 votes
4 answers
614 views

Can something like a Donkey Sentence exist in a programming language?

I am interested, whether, in some programming language, there can be something like a Donkey Sentence, a sentence that defies straightforward attempts to translate it into a formal language, but is ...
FlatAssembler's user avatar
8 votes
3 answers
159 views

Relative precedence of let and if expressions

In a language with standard let and if expressions, what should be the their precedence such that they can be nested without parentheses? For example, I want to be able to parse both of these ...
Panda's user avatar
  • 249
-5 votes
1 answer
113 views

What kind of a lexer (tokenizer) and parser would be useful for standardizing mailing addresses? [closed]

This is a question about designing and implementing a language of street addresses. In the input high-level interface language, many syntaxes are allowed. In the output low-level implementation ...
Samuel Muldoon's user avatar
8 votes
1 answer
431 views

How are hand-written parsers organised, and how do they work?

Below, we have an example of two extremely simple languages and a relationship between the two languages: Inputlanguage (-1, 0) (0, 1) (1, 0) (0, 1) (0, -1) (1, 0) (1, 0) Outputlanguage "left&...
Samuel Muldoon's user avatar
5 votes
2 answers
134 views

What is it that makes parsing shell so hard?

Parsing shell scripts is notoriously challenging. There is a long history of subtle parsing bugs in implementations (e.g.), some of them long-lived, and of static analysis tools that settle for very ...
Michael Homer's user avatar
  • 12.9k
4 votes
2 answers
138 views

In a grammar specification, how to exclude characters?

I want to specify in my grammar that an identifier could be any character except for a list of characters (that is have a deny list instead of the most common allow list). I've seen the common ...
OscarRyz's user avatar
  • 199
5 votes
1 answer
96 views

How would I allow a variety of different syntaxes for passing arguments into MathJax or LaTeX commands? [closed]

What is LaTeX If you already know what LaTeX is, then skip down the the section labeled "sloppy syntax". There is a type-setting language known as LaTeX. LaTeX even has its very own Stack ...
Samuel Muldoon's user avatar
5 votes
1 answer
123 views

Context-free grammar for a language where indentation marks code blocks?

I have the following context-free grammar: ...
mousetail's user avatar
  • 8,229
10 votes
1 answer
252 views

How to parse a language where functions are full sentences?

I'm designing a language that looks like this: ...
mousetail's user avatar
  • 8,229
8 votes
1 answer
152 views

When should I use a hand-written parser over a parsing library?

There are plenty of libraries out there that provide tools like LL parsers, combinator parsers, ebnf parsers and more. However, these may not always be suited to the grammar of a programming language. ...
lyxal's user avatar
  • 1,775
9 votes
1 answer
189 views

How to distinguish custom operators from each other?

How might one go about building a parser that can distinguish custom operators in prefix, infix or postfix positions. For example: ...
kaiserthe13th's user avatar
8 votes
3 answers
182 views

Representing parenthesis in an AST

This language is implemented in Rust using a lot of enums for things like expressions. Some of the planned validation rules involve checking how parenthesis are used -- where they're needed and are ...
0xLogN's user avatar
  • 180
5 votes
1 answer
369 views

How exactly does requiring a semicolon after `EndIf` and `EndWhile` make recovering from parsing errors easier?

In my programming language, AEC, unlike in Ada or VHDL, there is no semicolon after the EndIf token. That is, you can put the semicolon ...
FlatAssembler's user avatar
12 votes
2 answers
881 views

What is the difference between an Abstract Syntax Tree and a Parse Tree?

Compiling and interpreting programming languages typically involves parsing text into a tree that represents the different groupings of syntactic elements. The hierarchy represents which syntactic ...
CPlus's user avatar
  • 8,261
10 votes
5 answers
245 views

Allowing `}` as a statement terminator in an expression-based language?

My language is expression based; many of its language constructs are not statements, but rather expressions that return a value. However, since everything is an expression, my grammar looks like ...
bigyihsuan's user avatar
  • 1,821