Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Parsing with incomplete grammars

Are there any common solutions how to use incomplete grammars? In my case I just want to detect methods in Delphi (Pascal)-files, that means procedures and functions. The following first attempt is working

    methods
      : ( procedure | function | . )+
      ;

but is that a solution at all? Are there any better solutions? Is it possible to stop parsing with an action (e. g. after detecting implementation). Does it make sense to use a preprocessor? And when yes - how?

like image 839
ANTLRStarter Avatar asked Aug 26 '11 11:08

ANTLRStarter


2 Answers

If you're only looking for names, then something as simple as this:

grammar PascalFuncProc;

parse
  :  (Procedure | Function)* EOF
  ;

Procedure
  :  'procedure' Spaces Identifier
  ;

Function
  :  'function' Spaces Identifier
  ;

Ignore
  :  (StrLiteral | Comment | .) {skip();}
  ;

fragment Spaces     : (' ' | '\t' | '\r' | '\n')+;
fragment Identifier : ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9')*;
fragment StrLiteral : '\'' ~'\''* '\'';
fragment Comment    : '{' ~'}'* '}';

will do the trick. Note that I am not very familiar with Delhpi/Pascal, so I am surely goofing up StrLiterals and/or Comments, but that'll be easily fixed.

The lexer generated from the grammar above will only produce two type of tokens (Procedures and Functions), the rest of the input (string literals, comments or if nothing is matched, a single character: the .) is being discarded from the lexer immediately (the skip() method).

For input like this:

some valid source
{ 
  function NotAFunction ...
}

procedure Proc
Begin
  ...
End;

procedure Func
Begin
  s = 'function NotAFunction!!!'
End;

the following parse tree is created:

enter image description here

like image 184
Bart Kiers Avatar answered Oct 22 '22 16:10

Bart Kiers


What you asking about are called island grammars. The notion is that you define a parser for the part of the language you care about (the "island") with all the classic tokenization needed for that part, and that you define an extremely sloppy parser to skip the rest (the "ocean" in which the island is embedded). One common trick to doing this is to define correspondingly sloppy lexers, that pick up vast amounts of stuff (to skip past HTML to embedded code, you can try to skip past anything that doesn't look like a script tag in the lexer, for example).

The ANTLR site even discusses some related issues but notably says there are examples included with ANTLR. I have no experience with ANTLR so I don't know how useful this specific information is.

Having built many tools that use parsers to analyze/transform code (check my bio) I'm a bit of a pessimist about the general utility of island grammmars. Unless your goal is to do something pretty trivial with the parsed-island, you will need to collect the meaning of all identifiers it uses directly or indirectly... and most of them are unfortunately for you defined in the ocean. So IMHO you pretty much have to parse the ocean too to get past trivial tasks. You'll have other troubles, too, making sure you really skip the island stuff; this pretty much means your ocean lexer has know about whitespace, comment, and all the picky syntax of character strings (this is harder than it looks with modern languages) so that these get properly skipped over. YMMV.

like image 4
Ira Baxter Avatar answered Oct 22 '22 16:10

Ira Baxter