Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That claim about the Wirth languages surprises me, because AFAIK all of his compilers used a lexer (called like get_next_token()) and you'd need to look at multiple characters to e.g. tell an identifier apart from a keyword. Maybe you're thinking of how his grammars only need one token of lookahead -- they're LL(1)?

I guess I'm quibbling. I do agree that they seem easy to parse with a scannerless parser too.



I think you're right that Wirth's own compilers usually used a lexer.

And you're right, you do need one token lookahead, not just one character, in a few places if you insist on entirely unambiguous symbols immediately.

The point is that it's not necessary, as the few places where there is ambiguity while looking at only a single character, it's sufficiently unambiguous that it doesn't matter until after you've parsed enough to be able to discrimate it.

E.g. this is from Oberon:

    statement  =  [assignment | ProcedureCall | 
        IfStatement | CaseStatement | WhileStatement | RepeatStatement | 
        LoopStatement | WithStatement | EXIT | RETURN [expression] ].
All of the above except "assignment" and "ProcedureCall" starts with a keyword. ProcedureCall and assignment both starts with productions that ultimately starts with an "ident".

So you can parse it like this (Ruby-ish pseudocode)

    ident = parse_ident
    if !ident
       # throw error here
    end
    case ident
      when :if
        return parse_if
      when :case
        return parse_case
      ... and so on ..
      else
        return parse_assignment_or_procedurecall(ident)
    end
So you know that you are dealing with a valid program as long as you find an "ident".

It is still often cleaner to simply use a lexer vs. doing something like the above example of passing "ident" to a subroutine, or adding backtracking ("unget") support to the parser, so I'm not suggesting it's always a good choice to forgo a separate lexer, but the languages means you can.

In particular, if you don't want to add backtracking, even if it'll rarely be many characters, you'll need to "unroll" the grammar more, like with the "parse_assignment_or_procedurecall" example, and that can get messy, but it works fine.

E.g. in the above case:

    assignment     =  designator ":=" expression. 
    ProcedureCall  =  designator [ActualParameters].

    designator  =  qualident {"." ident | "[" ExpList "]" | "(" qualident ")" | "^" }. 
    qualident  =  [ident "."] ident. 
So "parse_assignment_or_procedurecall(ident)" would for the most part be relatively simple, and the one complication is unaffected by whether you use a lexer or not, and actually probably the most tricky production I've seen in a Wirth grammar to the point where merging the parsing of the two is probably simpler - ActualParameters is a strict superset of "(" qualident ")" I believe, so as long as you keep seeing "(", you expect either just a qualident or a list of expressions; once you see something that isn't just a qualident followed by ")", you're at the end of a ProcedureCall or have an error.




Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: