[antlr-interest] Compression of dfa tables
Andreas Jonsson
aj at member.fsf.org
Thu Aug 5 13:59:56 PDT 2010
2010-08-05 18:21, Jim Idle skrev:
> The size of the DFA tables is known about, but despite cache misses, you
> won't notice the effect unless you have huge inputs, in which case there
> will be plenty of other cache misses anyway. However, when you end up with a
> large DFA set, it usually (not always) means that the lexer can be specified
> 'better' (in terms of allowing ANTLR to deal with it better).
>
>
That sounds reassuring. But I thought that the cache misses was mostly
depending on how varying the input is?
> Can you post your grammar so we can see it?
>
>
Certainly. I'll post what I have below. Funny thing is that the size
of the lexer have suddenly decreased to 2MB.
I have taken upon me the perhaps foolish task of attempting to write a
parser for MediaWiki. The wikitext have the property that any sequence
of bytes is valid input, and MediaWiki's wikitext is inherently not
context free. So, I'm using the antlr generated parser as a front-end
that interacts with a context object.
I'm currently working on the table parsing. If anyone have any ideas on
how to do things differently, I would be greatful to hear it.
/Andreas
/*
* Copyright 2010 Andreas Jonsson
*
* This file is part of libmwparser.
*
* Libmwparser is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
grammar mw;
options {
language = C;
k = 1;
}
@lexer::preincludes {
struct MWKEYVALUE_struct;
}
@lexer::includes {
#include <mwparsercontext.h>
}
@parser::includes {
#include <mwparsercontext.h>
}
@lexer::members{
#define X ((MWPARSERCONTEXT*)(ctx->pLexer->super))
#define BOL (LEXER->input->charPositionInLine <= 0)
static pANTLR3_COMMON_TOKEN newToken(pANTLR3_TOKEN_FACTORY factory,
ANTLR3_UINT32 type, pANTLR3_STRING text)
{
pANTLR3_COMMON_TOKEN t = factory->newToken(factory);
t->setType(t, type);
t->setText(t, text);
return t;
}
#define D(msg) (fputs(msg, stderr), fputc('\n', stderr),
printLexerInfo(LEXER), true)
#define NEW_TOK(type, text) (newToken(LEXSTATE->tokFactory, type, text))
#define SUBSTR1(start) (INPUT->substr(INPUT, start, GETCHARINDEX() - 1))
#define SUBSTR2(start, end) (INPUT->substr(INPUT, start, end))
}
@parser::members{
#define X ((MWPARSERCONTEXT*)(ctx->pParser->super))
#define INLINE_ELEMENT(code) if (!X->inlinePrescan) { code } else {
X->onInlineTokenPrescan(X, LT(-1)); }
#define D(msg) (fputs(msg, stderr), fputc('\n', stderr),
printParserInfo(PARSER), true)
}
article: NEWLINE* blocks NEWLINE* EOF
;
blocks: block ((NEWLINE)=> NEWLINE)* blocks?
;
block: paragraph | table
;
paragraph: {X->beginParagraph(X);} inline_text ((NEWLINE
inline_element)=> NEWLINE inline_text)* {X->endParagraph(X);}
;
inline_text: inline_prescan actual_inline_text
;
inline_prescan
@init {
ANTLR3_MARKER mark;
}:
{
mark = MARK();
X->beginInlinePrescan(X);
}
((inline_element)=> inline_element)+
{
X->endInlinePrescan(X);
REWIND(mark);
}
;
actual_inline_text: ((inline_element)=>inline_element)+
;
inline_element: (format|special|space|word|nowiki|html_entity)
;
special: (SPECIAL | apostrophes) {INLINE_ELEMENT(X->onSpecial(X, $text);)}
;
space: ((SPACE_TAB)=> SPACE_TAB)+ {INLINE_ELEMENT(X->onSpace(X, $text);)}
;
word: WORD {INLINE_ELEMENT(X->onWord(X, $text);)}
;
html_entity: HTML_ENTITY {INLINE_ELEMENT(X->onHTMLEntity(X, $text);)}
;
newline: NEWLINE {INLINE_ELEMENT(X->onNewline(X);)}
;
nowiki : NOWIKI {INLINE_ELEMENT(X->onNowiki(X, $text);)}
;
format: ({!X->inlinePrescan}?=> (bold | italic)
{X->onConsumedApostrophes(X);});
apostrophes: (apostrophe)+ { if(X->inlinePrescan) {
X->onApostrophesPrescan(X, $text); } };
bold: {X->takeBold}?=> (begin_bold | end_bold);
italic: {X->takeItalic}?=> (begin_italic | end_italic);
apostrophe: {X->inlinePrescan}?=> A
| {X->takeApostrophe}?=> A {X->onConsumedApostrophes(X);} ;
begin_bold: {!X->inBold}?=> A A A {X->beginBold(X);} ;
end_bold: { X->inBold}?=> A A A {X->endBold(X);} ;
begin_italic: {!X->inItalic}?=> A A {X->beginItalic(X);};
end_italic: { X->inItalic}?=> A A {X->endItalic(X);} ;
table: begin_table table_rows end_table
;
begin_table: begin = BEGIN_TABLE NEWLINE* (garbage_inline_text
NEWLINE*)* {X->beginTable(X, $begin->custom);}
;
garbage_inline_text: inline_text
;
end_table: (END_TABLE | EOF) {X->endTable(X);}
;
table_rows: ((~(BEGIN_TABLE_COLUMN|TABLE_ROW_SEPARATOR))=> table_first_row)?
((TABLE_ROW_SEPARATOR)=> table_row)*
;
table_first_row: table_row_content
;
table_row: TABLE_ROW_SEPARATOR table_row_content
;
table_row_content: table_columns
;
table_columns: table_column*
;
table_column: BEGIN_TABLE_COLUMN
;
NOWIKI
@init {
ANTLR3_MARKER nowikiStart;
ANTLR3_MARKER nowikiEnd;
}
:
'<nowiki>'
((SPACE_CHAR|NEWLINE_CHAR) => (SPACE_CHAR|NEWLINE_CHAR))*
{ nowikiStart = GETCHARINDEX(); }
NOWIKI_BODY[&nowikiEnd]
{ SETTEXT(SUBSTR2(nowikiStart, nowikiEnd)); }
;
fragment
NOWIKI_BODY[ANTLR3_MARKER *nowikiEnd]:
(((SPACE_CHAR|NEWLINE_CHAR)* ('</nowiki>'|EOF))=>
(SPACE_CHAR|NEWLINE_CHAR)* ('</nowiki>'|EOF) )
|
({ *nowikiEnd = GETCHARINDEX(); } . ) NOWIKI_BODY[nowikiEnd]
;
BEGIN_TABLE @init{pANTLR3_VECTOR attrs = NULL;}: {BOL ||
X->prevTokenWasIndent(X, GETCHARINDEX())}?=>
SPACE_TAB* '{|' { X->onBeginTableToken(X);}
ATTRIBUTES[&attrs]
{ CUSTOM = attrs; }
;
END_TABLE: {BOL && X->inTable(X)}?=>
(SPACE_TAB)* '|}' {X->onEndTableToken(X);}
;
TABLE_ROW_SEPARATOR @init{pANTLR3_VECTOR attrs = NULL;}:
{BOL && X->inTable(X)}?=> ((SPACE_TAB)* '|-') => (SPACE_TAB)* '|'
(('-')=>'-')+
ATTRIBUTES[&attrs]
{ CUSTOM = attrs; }
;
BEGIN_TABLE_COLUMN @init{pANTLR3_VECTOR attrs = NULL;}: {BOL &&
X->inTable(X)}?=>
(SPACE_TAB)* '|' {attrs = NULL;} ATTRIBUTE_LIST[&attrs] ('|'
~('|'))=>
{ CUSTOM = attrs; }
;
fragment
ATTRIBUTES[pANTLR3_VECTOR *attrs]:
((SPACE_TAB)=> SPACE_TAB)*
((ATTRIBUTE_LIST[NULL])=> ATTRIBUTE_LIST[attrs])?
((~(NEWLINE_CHAR))=> .)* (NEWLINE | EOF)
;
fragment
ATTRIBUTE_LIST[pANTLR3_VECTOR *attrs] @init{MWKEYVALUE attr;}:
( (ATTRIBUTE[NULL] (SPACE_TAB)+ ATTRIBUTE[NULL])=>
ATTRIBUTE[&attr] (SPACE_TAB)+ ATTRIBUTE_LIST[attrs]
| ATTRIBUTE[&attr] )
{
MWKEYVALUE *p = ANTLR3_MALLOC(sizeof(*p));
*p = attr;
if (*attrs == NULL) {
*attrs=X->vectorFactory->newVector(X->vectorFactory);
}
(*attrs)->add(*attrs, p, ANTLR3_FREE_FUNC);
}
;
fragment
ATTRIBUTE[struct MWKEYVALUE_struct *attr]:
ATTRIBUTE_NAME[&attr->key] SPACE_TAB* '=' SPACE_TAB*
ATTRIBUTE_VALUE[&attr->value];
fragment
ATTRIBUTE_NAME[pANTLR3_STRING *name] @init{ ANTLR3_MARKER start; }:
{ start = GETCHARINDEX(); }
(('xml:'|'xmlns:')? (LETTER|DECIMAL_DIGIT))+
{ *name = SUBSTR1(start); }
;
fragment
ATTRIBUTE_VALUE[pANTLR3_STRING *value] @init{ ANTLR3_MARKER start; }:
{ start = GETCHARINDEX(); }
(
('"'
{ start = GETCHARINDEX(); }
~('"' |'<')+
{ *value = SUBSTR1(start);}
'"' )
| ('\''
{ start = GETCHARINDEX(); }
~('\''|'<')+
{ *value = SUBSTR1(start);}
'\'')
// Regexp from Sanitizer.php:
[a-zA-Z0-9!#$%&()*,\\-.\\/:;<>?@[\\]^_`{|}~]
| { start = GETCHARINDEX(); }
|
(LETTER|DECIMAL_DIGIT|'!'|'#'|'$'|'%'|'&'|'('|')'|'*'|','|'-'|'.'
|'/'|':'|';'|'<'|'>'|'?'|'@'|'['|']'|'^'|'_'|'`'|'{'|'|'|'}'|'~')+
{ *value = SUBSTR1(start);}
// This case (from Sanitizer.php) can never be matched as it
is already covered by
// the previous case:
// (\#[0-9a-fA-F]+) # Technically wrong, but lots of
// # colors are specified like this.
// # We'll be normalizing it.
// | '#' HEX_DIGIT+
)
;
HTML_ENTITY:
'&' HTML_ENTITY_CHARS ';'
| '&#' DECIMAL_NUMBER ';'
| '&#x' HEX_NUMBER ';'
;
WORD: CHAR+
;
SPACE_TAB: /* { X->spaceTabEnabled}?=> */ (SPACE_CHAR | TAB_CHAR)+ ;
//SPACE: {!X->spaceTabEnabled}?=> SPACE_CHAR+ ;
//TAB: {!X->spaceTabEnabled}?=> TAB_CHAR+ ;
NEWLINE: '\r\n' | '\n\r' | NEWLINE_CHAR {X->onNewlineToken(X);};
SPECIAL: SPECIAL_SYMBOL+
;
A: '\'';
fragment CHARACTER: WHITESPACE_CHAR | NON_WHITESPACE_CHAR |
HTML_ENTITY;
fragment WHITESPACE: WHITESPACE_CHAR+;
fragment WHITESPACE_CHAR: SPACE_CHAR ;
fragment TAB_CHAR: '\t' | '\xB0';
fragment SPACE_CHAR: ' ';
fragment NEWLINE_CHAR: '\n' | '\r';
fragment NEWLINES: NEWLINE+;
fragment NON_WHITESPACE_CHAR: ~(SPACE_CHAR | TAB_CHAR | NEWLINE_CHAR);
fragment LETTER: UCASE_LETTER | LCASE_LETTER;
fragment HTML_ENTITY_CHARS: HTML_ENTITY_CHAR+;
fragment HTML_ENTITY_CHAR: UCASE_LETTER | LCASE_LETTER | DECIMAL_DIGIT;
fragment UCASE_LETTER: 'A'..'Z';
fragment LCASE_LETTER: 'a'..'z';
fragment HTML_UNSAFE_SYMBOL: '<' | '>' | '&';
fragment UNDERSCORE: '_';
fragment DECIMAL_NUMBER: DECIMAL_DIGIT+;
fragment DECIMAL_DIGIT: '0'..'9';
fragment HEX_NUMBER: HEX_DIGIT+;
fragment HEX_DIGIT: DECIMAL_DIGIT | ('A'..'F') | ('a'..'f');
fragment SPECIAL_SYMBOL: '!'|'"'|'#'|'$'|'%'|'&'|'('|
')'|'*'|'+'|','|'-'|'.'|'/'|':'|
';'|'<'|'='|'>'|'?'|'@'|'['|'\\'|
']'|'^'|'_'|'`'|'{'|'|'|'}'|'~';
fragment
CHAR: ~(SPECIAL_SYMBOL|SPACE_CHAR|TAB_CHAR|NEWLINE_CHAR|A);
More information about the antlr-interest
mailing list