ЛЛ(1) токенизатор для Лиспа


Я пытаюсь написать интерпретатор Лиспа на C#, так что я начал с разметки. Я еще не дочитал до конца (нужно обрабатывать числа с плавающей точкой и символы), но я уже переписал его два раза потому что я не могу не довольны дизайном.

    public class TokenizerException : System.ApplicationException
{
    public TokenizerException() {}
    public TokenizerException(string message) {}
    public TokenizerException(string message, System.Exception inner) {}

    // Constructor needed for serialization 
    // when exception propagates from a remoting server to the client.
    protected TokenizerException(System.Runtime.Serialization.SerializationInfo info,
        System.Runtime.Serialization.StreamingContext context) {}
}
public abstract class Token
{
    public string val;
    public Token(string val)
    {
        if(val != null) this.val = val;
        else this.val = "";
    }
}
class OpenParenToken: Token 
{
    public OpenParenToken(string value) : base(value) {}        
}
class CloseParenToken: Token 
{
    public CloseParenToken(string value) : base(value) {}
}
class NumberToken: Token 
{
    public NumberToken(string value) : base(value) {}
}
class StringToken: Token 
{
    public StringToken(string value) : base(value) {}
}
class IdToken: Token 
{
    public IdToken(string value) : base(value) {}
}
class SymbolToken: Token 
{
    public SymbolToken(string value) : base(value) {}
}


public class Tokenizer
{

    private const string parens = "([])";
    private string code;
    private char ch;
    private object token;
    private List<Token> tokens;

    private int p = 0;

    public Tokenizer(string code)
    {
        this.code = code;
        tokens = new List<Token>();
    }

    private char getCh()
    {
        ch = code[p];
        return ch;
    }

    public void DumpTokens()
    {
        foreach(object t in tokens)
        {
            Console.Write("<"+t.GetType()+", "+(t as Token).val+"> ");
        }
        Console.WriteLine();
    }

    private char NextCh()
    {
        if(p >= code.Length) throw new TokenizerException("End of input reached, cant get more chars");
        ch = getCh();
        if(char.IsWhiteSpace(ch)) { p++; return NextCh(); }
        else return ch;
    }

    private Token NextParenToken(char ch)
    {
        Token t;
        if(parens.IndexOf(ch) <= parens.Length/2)
        {
            t = new OpenParenToken(ch.ToString());
        }
        else t = new CloseParenToken(ch.ToString());
        tokens.Add(t);
        return t;
    }

    private Token NextNumberToken()
    {
        int startPos = p;
        while(p < code.Length)
        {
            char c = getCh();
            if(!char.IsDigit(c)) break;
            p++;
        }
        p--;
        NumberToken n = new NumberToken(code.Substring(startPos, p - startPos + 1));
        tokens.Add(n);
        return n;
    }

    private Token NextStringToken()
    {
        if(p + 1 > code.Length) throw new TokenizerException("Unmatched \" at the end of the code");
        int startPos = ++p;
        while(p < code.Length)
        {
            char c = getCh();
            if(c == '\"') break;
            p++;
        }

        StringToken t = new StringToken(code.Substring(startPos, p - startPos + 1));
        tokens.Add(t);
        return t;
    }

    private Token NextIDToken()
    {
        int startPos = p;
        while(p < code.Length)
        {
            getCh();
            if(parens.IndexOf(ch) > parens.Length/2 || char.IsWhiteSpace(ch)) break;
            if(parens.IndexOf(ch) >= 0 && parens.IndexOf(ch) <= parens.Length/2) throw new TokenizerException("Bad identifier at " + p);
            p++;
        }
        p--;
        string id = code.Substring(startPos, p - startPos + 1);
        IdToken t = new IdToken(id);
        tokens.Add(t);
        IdTable.insert(id, t);

        return t;
    }

    public Token NextToken()
    {
        char ch = NextCh();
        if(parens.Contains(ch))
        {
            return NextParenToken(ch);
        }

        if(char.IsDigit(ch))
        {
            return NextNumberToken();
        }

        if(ch == '\"')
        {
            return NextStringToken();
        }

        // identifiers
        return NextIDToken();
    }

    public void Lex()
    {
        tokens.Clear();
        for(p=0; p < code.Length; p++)
        {
            NextToken();
        }
    }

}


1641
12
задан 7 февраля 2011 в 07:02 Источник Поделиться
Комментарии
3 ответа

В adition к Snowbear по пунктам:

1) я не использую иерархии наследования для маркера, вместо этого я найти его более удобным, чтобы использовать свойство перечисление на маркер, чтобы определить тип.

2) Вы могли бы хотеть думать о "чтении" пробел в знак того, что просто не возвращается (это расширение точки Snowbear о не используя рекурсию, чтобы прочитать следующий символ).

3) ЛЛ(1) является термин, который относится к парсерам, не сканеры (tokenisers).

4) я также люблю выполнять мои сканеры как IEnumerator, который принимает строку, чтобы быть отсканированы в конструктор ... но это просто дело личного вкуса. :)

8
ответ дан 8 февраля 2011 в 01:02 Источник Поделиться

1) я хотел бы удалить строку вал из базы жетон класса, он пахнет, как большая набирается код. Ваши наследники могут иметь более конкретную информацию, например количество маркеров может обеспечить двойное вместо строки
2) общественные строку вал; - Паскаль чехол для публичных свойств является правилом .Чистая
3) Если(val != null) это.вал = вал; еще.Валь = ""; это длинная форма:
это.вал = вал ?? "";
4) частная Чаре NextCh() рекурсия не имеет смысла здесь, регулярный цикл-это более чем достаточно.
5) не нашел какого-либо смысла в этой области: частные тип char ч;, ты его как локальную переменную везде. Это поле должно быть удалено.
6) код поля могут быть сделаны только для чтения
7) функцией getch() одна строка должна быть удалена
8) поле маркера должны быть удалены, поскольку это, кажется, не используется и не имеет никакого смысла в токенизатор контексте
9) является IdTable одноэлементный? Синглтоны-это зло.
10) строку.Метод indexOf(с) тут же, как это

    while(p < code.Length)
{
char c = getCh();
if(c == '\"') break;
p++;
}`

11) ваши фокусы со скобками и помощи indexOf <= Длина/2 не улучшают читабельность на всех
12) ИМО, ваш класс тоже с состояниями, при анализе лексем в каждом методе вы должны иметь в виду все те поля, которые вы имеете в своем классе. Я бы порекомендовал удалить, а не все поля и параметров метода.

5
ответ дан 8 февраля 2011 в 12:02 Источник Поделиться

Главное замечание это то, что я думаю, что C# - это неправильный язык выбрать для маркирования язык. Его вполне хорошим для основной массы интерпретатор Лиспа, но один из главных навыков инженер-программист выбирает правильный язык для работы. Не только простота, но простота обслуживания и будущей работы.

Сейчас мне лично нравится Лекс, но есть и другие лексические генераторов там. Но я просто хочу показать вам, как простой Lex файл. Даже если вы не знаете точный синтаксис Лекс достаточно прост, что большинство людей сразу же сможете прочитать (если в CS фон) и даже самые сложные модификации может быть сделано в течение часа дали соответствующую книгу.

ОК я не уверен на 100% точных правил маркировки сюсюкать.

DIGIT           [0-9]
NUMBER [+-]?{DIGIT}+
EXP [EeDd]{NUMBER}
IDTOKEN [^)(; \t\v\r]
IDENTIFIER {IDTOKEN}+
SPACE [ \t\v\r]

%x STRING COMMENT
%%

; { BEGIN(COMMENT); }
<COMMENT>[^\n]+ { /* IGNORE */ }
<COMMENT>\n { BEGIN(INITIAL); }

{NUMBER} { return CONSTANT_NUMBER_INT; }

{NUMBER}{EXP} { return CONSTANT_NUMBER_FLOAT; }
{NUMBER}?"."{DIGIT}+{EXP}? { return CONSTANT_NUMBER_FLOAT; }
{NUMBER}"."{DIGIT}*{EXP}? { return CONSTANT_NUMBER_FLOAT; }

{NUMBER}\/{NUMBER} { return CONSTANT_NUMBER_RATIO; }

\" { BEGIN(STRING); yymore(); }
<STRING>[^\"\\\n]+ { yymore(); }
<STRING>\\. { yymore(); }
<STRING>\" { BEGIN(INITIAL); return CONSTANT_STRING; }
<STRING>\n { error("NewLine inside string");}

{IDENTIFIER} { return NAME; }

\( { return '('; }
\) { return ')'; }

\n { lineCount++; }
{SPACE}+ { /* Ignore Space */ }

%%
/* Add this rule if there are things that can't match
* But Lisp seems to be very flexible on Identifier
* names so it seems like it is not required.
. { error("Unknown character"); }
*/

50 строк-это гораздо легче читать, чем 200.

3
ответ дан 8 февраля 2011 в 04:02 Источник Поделиться