5 ms·

I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand. They're still separate modul

• deleted 3y ago
  [deleted]
• Twisol 3y ago
  > I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand. You even get this for free in a lazy language like Haskell, where your parser can accept a list of tokens `[Token]` whilst the list itself is only computed on-demand whenever the parser tries to get the next one. Well, except for the context-sensitive option: > (and as a consequence, it's natural to let lexing be context-sensitive where needed).
  • beached_whale 3y ago
    This is how I am setup in the little language I am writing in C++. I put the lexer into an iterator.
• matheusmoreira 3y ago
  > I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand. This is how I implemented it in my language. Evaluator asks parser for a value, parser asks lexer for one or more tokens, lexer asks the I/O layer for characters. It's nice.
• bazoom42 3y ago
  A Javascript parser have to do something like this. The text /a/ tokenize differently depending on where in the grammar, eg a/b/c is division (/a/) is a regex.
  • OJFord 3y ago
    That's not unusual though and can just be normal lexing (or parsing - IMO it can be a pretty arbitrarily drawn line) e.g. in many languages = 'tokenises differently depending on where it is in the grammar': a = b is assignment; a == b is an equality test.
    • whizzter 3y ago
      No, = or == is purely a lexer decision easily decided by greedy _character_ matching and easily resolved. In JavaScript the following give wildly differently shaped ASTs since the / character initiates RegEx parsing when in a _value position_ that has different lexing than the division operator that _only_ appears as a potential binary operator, consider the following: a = b + /c.y/+d a = b /c.y/+d (Given b=1 , c={y:2} and d=3 ) The first assigns a as add b to the RegExp matching c.y added to +d giving us the string "1/c.y/3" (JS converts most types to string on addition and strings are dominant during addition as concatenations), this is correct since the + operator before the / character forces the parser to look for a value. The second reads as assign a to b divided by property y of c then divided by d (ie the numeric computation (1/2)/3 = 0.166666.... ), this is because the parser is looking for binary operators after the b identifier and when the / character appears it becomes an operator. So, without knowing the parsing context (operator or value position) the lexer decision is ambigious. This is somewhat how A<B<C>> is ambigious when parsing C++/Java/C# templates/generics VS the <, > and >> operators but that case is usually easier since the parser could include a hack in the generic parsing code that mutates the token stream if it encounters >> when closing a generic. (The JS ambiguity is worse though since RegEx lexing rules are totally different from regular JS)
      • OJFord 3y ago
        True; but the division vs regex example that I replied to was also 'easily decided bg greedy character matching and easily resolved. I don't know how JS (implementations) actually does it, but this is what I meant by the line being a bit arbitrary, in my limited experience - you can just lex 'forward slash token' or whatever and keep your lexer/parser separation even with this ambiguity.