Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm working on a toy compiler (for some simple language like PL/0) and I have my lexer up and running. At this point I should start working on building the parse tree, but before I start I was wondering: How much information can one gather from just the string of tokens? Here's what I gathered so far:

  1. One can already do syntax highlighting having only the list of tokens. Numbers and operators get coloured accordingly and keywords also.
  2. Autoformatting (indenting) should also be possible. How? Specify for each token type how many white spaces or new line characters should follow it. Also when you print tokens modify an alignment variable (when the code printer reads "{" increment the alignment variable by 1, and decrement by 1 for "}". Whenever it starts printing on a new line the code printer will align according to this alignment variable)
  3. In languages without nested subroutines one can get a complete list of subroutines and their signature. How? Just read what follows after the "procedure" or "function" keyword until you hit the first ")" (this should work fine in a Pascal language with no nested subroutines)
  4. In languages like Pascal you can even determine local variables and their types, as they are declared in a special place (ok, you can't handle initialization as well, but you can parse sequences like: "var a, b, c: integer")
  5. Detection of recursive functions may also be possible, or even a graph representation of which subroutine calls who. If one can identify the body of a function then one can also search if there are any mentions of other function's names.
  6. Gathering statistics about the code, like number of lines, instructions, subroutines

EDIT: I clarified why I think some processes are possible. As I read comments and responses I realise that the answer depends very much on the language that I'm parsing.

share|improve this question
5  
No, you cannot do any decent highlighting using just tokens - you'll miss all the context-sensitive semantics. Autoidentation is not possible as well, you'll need some semantic information. And, what's the point? In the modern parsing approaches you'll even skip lexing altogether. –  SK-logic Nov 28 '12 at 13:59
3  
@SK-logic: Not sure what "modern parsing approaches" you're thinking of, but skipping the lexing phase and trying to fold all that logic into the parser itself is a great way to screw it up. –  Mason Wheeler Nov 28 '12 at 14:02
4  
@MasonWheeler, you're wrong, and your link does not prove anything (besides DBXJSON authors ignorance). All the PEG-based parsers are naturally lexerless, and it is really great. Now you're not limited to a boring, flat sequence of tokens - you can easily mix different languages in a single input stream. And it benefits even things like parsing printf format strings, not just advanced languages like Katahdin. –  SK-logic Nov 28 '12 at 14:06
2  
"you can easily mix different languages": From a formal language point of view, the union or intersection of different languages is just another language. In this respect, I do not see how skipping the lexical analysis phase can make parsing easier. –  Giorgio Nov 28 '12 at 14:10
2  
@Giorgio, you're so wrong. How can you define a comment (i.e., a whitespace token) this way?!? Your Pascal parser will choke on these { } tokens. There is absolutely no way to unify two different languages' sets of tokens. A single token in one language will be many different tokens in the other. Think of, say, Verilog numeric constants. And, needless to mention, you won't be able to extend your language with the new syntax dynamically if you're using a dedicated lexing pass. –  SK-logic Nov 28 '12 at 14:18

1 Answer 1

You've got one minor problem with your definitions there. Auto-formatting and recursive function definition (and even variable detection) should not be possible in a lexer, because a lexer, by definition, is linear and context free. Its job is to read, identify and validate one single token, and then do it again and again and again until reaching the end of the file, and that's it.

Any recursive analysis, and anything that requires remembering state from before the beginning of the current token is beyond the scope of a lexer and should be undertaken in the parser instead. This separation of concerns makes your code cleaner and less likely to contain subtle bugs that are hard to track down.

share|improve this answer
1  
actually a lexer is regular ;), the syntax tree (in the parser) will be a context-free grammar –  ratchet freak Nov 28 '12 at 14:28
    
@RatchetFreak: I know. But each level of restrictions includes the restrictions of the level before. Therefore, all regular grammars must be not only linear, but also context free, which is the point I was making. –  Mason Wheeler Nov 28 '12 at 14:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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