0

This is kinda like a concrete version of the question Coming up with tokens for a lexer.

I'm writing a lexer for a small subset of HTML. I'm wondering what should I do when the input stream ends and I'm in a state where I've successfully recognized a token, but I know that it will be a syntax error.

I emphasise "I know" because this is the human me knowing, because I'm aware of the grammar rules which are "parser rules" (vs. "lexer rules"). I know that this is malformed: <b>hello</b, but there's nothing stopping the lexer from emitting the following.

Token: BEGIN-OPEN-TAG
Token: TAG-NAME           Value: b
Token: END-TAG
Token: DATA               Value: hello
Token: BEGIN-CLOSE-TAG    
Token: TAG-NAME           Value: b

Then parser would catch this as an error and report it. The reason I know that I can throw an error earlier is only because I'm aware of the parser and rules defined there. Do I get any benefit from marking this as invalid sequence of tokens, or should I try to keep such logic away from the lexer? When should a lexer emit an error anyway?

Should it allow <b<hello</b> then? How should a lexer handle a random < in the middle of the text: The \lt sign is <b><</b>? Backtracking? Or should I record it as [data] [<] [tagname] [>] [<] [</] [tagname] [>] and then let the parser know that [<] is valid in the middle of data?

The above are not questions which I expect an answer on, but more of a "if I decide on the question above, then it's an abyss of more blurred lines, which is why I'm having all these doubts". I'm having hard time deciding what should the lexer care about. If I make it care too much, I'm creating a parser at the same time. If I don't make it care enough, I'm pretty much making a "split at whitespace" procedure.

  • 2
    It may be desirable to look at the WHATWG living HTML standard which has an extensive section on parsing and tokenization. This standard documents agreement between major browsers, especially with regard to how such edge cases will be handled. – amon Dec 2 '18 at 19:43
9

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 benefit would be that illegal documents are recognized as illegal very slightly faster. That's not enough value for the high price.

Therefore you should keep your lexer as simple as possible, emitting primitives and not worrying its little head about syntax rules. Your code base will be much easier to understand if each component does one thing only.

2

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 assume you are parsing something akin to XHTML.

In theory we have a clean separation between lexer and parser: Lexer splits a text into a sequence of tokens and then the parser constructs a tree out of the tokens according to the grammar. Each component should throw an error if they are not able to complete its task. So a lexer should throw an error if it cannot produce a valid token (e.g. if there is an unclosed string, or a sequence of characters which is not a valid token), while grammatical errors from valid tokens should be detected by the parser.

There is no good reason to have the scanner detect errors which will be detected by the parser anyway, since this would be duplication of logic - which is a bad thing. (The parser might be slightly faster at detecting certain errors, but overall it would probably be slower overall if you have redundant checks, so you would be optimizing parsing invalid documents while penalizing parsing valid documents. Not a very good trade!)

But in reality many languages are designed in a way which makes it necessary to blur this clean separation. HTML does not have a single lexical grammar. It has at least two: one for tag content and one for cdata (the text outside of tags). For example the text Hello world would be two token inside a tag but one token as cdata. So the scanner need to at least keep track of most recent < or > in order to use the correct scanning mode.

Treating it as two distinct lexical grammars means << or <b< is a scanner-level error, because unquoted < is not a valid character inside a tag - it cannot produce a token.

But we still want to avoid duplication of logic, so if the scanner by necessity does the work of recognizing tags as units, there is no reason to throw that information away. Instead of emitting just sequence of tokens constituting a tag, the scanner could emit a tag as a structure contacting its tokens. The parser will then parse the constituent tokens into tagname and attributes and so on, and at the next level pair start and end tags up into a DOM-line tree structure.

1

It depends on the scope of your target language and your use cases. If you want to consider </b> (but not </ b>) as a keyword then the lexer can identify that as such. </b would probably get lexed as < / b, which the parser can then toss as < is unexpected token or no </b> for <b> which seems fine.

But it's probably better to just lex the characters and let the parser combine < / b > into a close tag. It allows you to reuse behavior to construct all of the close tags, making the behavior (and error conditions) more consistent. And generally the parser has more context to provide a nicer and more helpful error message than the lexer.

  • Oh, lex the < and / separately? I didn't think about that, given that most examples on C and such parse +, = and += as three separate tokens. In my head, </ is an opening bracket for a closing tag and I see it as a single token. – Lazar Ljubenović Dec 2 '18 at 19:43
  • 2
    @LazarLjubenović - well is it legal to put whitespace between? I don't actually know off hand. If not, then it makes sense to treat the combination as a single token. – Telastyn Dec 2 '18 at 19:50
0

Your lexer should catch syntax error for malformed tokens, and this solely. But in general, your tokens should be complex enough to avoid to return tokens which sole purpose is to delimit other token begin or end.

For example, it would be more practical to consider < *([a-zA-Z])+ *> as a single opening token, and let the lexer catch unknown tokens (such as <>). Treating it in the parser would lead to unecessary complex grammar rules. Your grammar rules will instead focus on ensuring proper enclosure of each tag.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.