Armen Mannes „Lexer“ für C #
https://stackoverflow.com/questions/673113
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, einen sehr einfachen Parser in C # zu schreiben.
Ich brauche einen Lexer - etwas, das mich assoziieren reguläre Ausdrücke mit Token lässt, so liest er in regexs und gibt mir Symbole zurück
.Es scheint, wie ich sollte in der Lage sein Regex zu verwenden, um die tatsächlichen schweres Heben zu tun, aber ich kann nicht eine einfache Möglichkeit sehen, es zu tun. Für eine Sache, Regex scheint nur auf Strings zu arbeiten, nicht-Streams (warum ist das!?!?).
Grundsätzlich möchte ich eine Implementierung der folgenden Schnittstelle:
interface ILexer : IDisposable
{
/// <summary>
/// Return true if there are more tokens to read
/// </summary>
bool HasMoreTokens { get; }
/// <summary>
/// The actual contents that matched the token
/// </summary>
string TokenContents { get; }
/// <summary>
/// The particular token in "tokenDefinitions" that was matched (e.g. "STRING", "NUMBER", "OPEN PARENS", "CLOSE PARENS"
/// </summary>
object Token { get; }
/// <summary>
/// Move to the next token
/// </summary>
void Next();
}
interface ILexerFactory
{
/// <summary>
/// Create a Lexer for converting a stream of characters into tokens
/// </summary>
/// <param name="reader">TextReader that supplies the underlying stream</param>
/// <param name="tokenDefinitions">A dictionary from regular expressions to their "token identifers"</param>
/// <returns>The lexer</returns>
ILexer CreateLexer(TextReader reader, IDictionary<string, object> tokenDefinitions);
}
So, Pluz senden die Codz ...
Nein, im Ernst, ich bin kurz vor dem Start eine Implementierung der obigen Schnittstelle Schreiben noch finde ich es schwer zu glauben, dass es nicht einige einfache Möglichkeit, dies zu tun, in .NET (2.0) bereits.
So, Vorschläge für einen einfachen Weg, um die oben zu tun? (Auch ich will keine „Code-Generatoren“. Die Leistung ist nicht wichtig für diese Sache und will ich nicht jede Komplexität in den Build-Prozess einzuführen.)
Lösung
Die ursprüngliche Version, die ich hier geschrieben als Antwort auf ein Problem hatte, dass es funktioniert nur, wenn es mehr als einen „Regex“ war, der den aktuellen Ausdruck abgestimmt. Das heißt, sobald nur ein Regex abgestimmt, wäre es ein Zeichen zurückgeben - während die meisten Menschen die Regex als „gierig“ wollen. Dies war besonders der Fall für Dinge wie „Anführungszeichen“.
Die einzige Lösung, die auf der Oberseite der Regex sitzt, ist den Eingang Zeile-für-Zeile zu lesen (was bedeutet, dass Sie nicht Token haben können, die über mehrere Zeilen erstrecken). Ich kann damit leben - es ist immerhin ein armer Mann Lexer! Außerdem ist es in der Regel sinnvoll Zeilennummer Informationen aus dem Lexer in jedem Fall zu erhalten.
So, hier ist eine neue Version, die diese Fragen behandelt werden. Kredit geht auch an dieser
public interface IMatcher
{
/// <summary>
/// Return the number of characters that this "regex" or equivalent
/// matches.
/// </summary>
/// <param name="text">The text to be matched</param>
/// <returns>The number of characters that matched</returns>
int Match(string text);
}
sealed class RegexMatcher : IMatcher
{
private readonly Regex regex;
public RegexMatcher(string regex) => this.regex = new Regex(string.Format("^{0}", regex));
public int Match(string text)
{
var m = regex.Match(text);
return m.Success ? m.Length : 0;
}
public override string ToString() => regex.ToString();
}
public sealed class TokenDefinition
{
public readonly IMatcher Matcher;
public readonly object Token;
public TokenDefinition(string regex, object token)
{
this.Matcher = new RegexMatcher(regex);
this.Token = token;
}
}
public sealed class Lexer : IDisposable
{
private readonly TextReader reader;
private readonly TokenDefinition[] tokenDefinitions;
private string lineRemaining;
public Lexer(TextReader reader, TokenDefinition[] tokenDefinitions)
{
this.reader = reader;
this.tokenDefinitions = tokenDefinitions;
nextLine();
}
private void nextLine()
{
do
{
lineRemaining = reader.ReadLine();
++LineNumber;
Position = 0;
} while (lineRemaining != null && lineRemaining.Length == 0);
}
public bool Next()
{
if (lineRemaining == null)
return false;
foreach (var def in tokenDefinitions)
{
var matched = def.Matcher.Match(lineRemaining);
if (matched > 0)
{
Position += matched;
Token = def.Token;
TokenContents = lineRemaining.Substring(0, matched);
lineRemaining = lineRemaining.Substring(matched);
if (lineRemaining.Length == 0)
nextLine();
return true;
}
}
throw new Exception(string.Format("Unable to match against any tokens at line {0} position {1} \"{2}\"",
LineNumber, Position, lineRemaining));
}
public string TokenContents { get; private set; }
public object Token { get; private set; }
public int LineNumber { get; private set; }
public int Position { get; private set; }
public void Dispose() => reader.Dispose();
}
Programm Beispiel:
string sample = @"( one (two 456 -43.2 "" \"" quoted"" ))";
var defs = new TokenDefinition[]
{
// Thanks to [steven levithan][2] for this great quoted string
// regex
new TokenDefinition(@"([""'])(?:\\\1|.)*?\1", "QUOTED-STRING"),
// Thanks to http://www.regular-expressions.info/floatingpoint.html
new TokenDefinition(@"[-+]?\d*\.\d+([eE][-+]?\d+)?", "FLOAT"),
new TokenDefinition(@"[-+]?\d+", "INT"),
new TokenDefinition(@"#t", "TRUE"),
new TokenDefinition(@"#f", "FALSE"),
new TokenDefinition(@"[*<>\?\-+/A-Za-z->!]+", "SYMBOL"),
new TokenDefinition(@"\.", "DOT"),
new TokenDefinition(@"\(", "LEFT"),
new TokenDefinition(@"\)", "RIGHT"),
new TokenDefinition(@"\s", "SPACE")
};
TextReader r = new StringReader(sample);
Lexer l = new Lexer(r, defs);
while (l.Next())
Console.WriteLine("Token: {0} Contents: {1}", l.Token, l.TokenContents);
Ausgabe:
Token: LEFT Contents: (
Token: SPACE Contents:
Token: SYMBOL Contents: one
Token: SPACE Contents:
Token: LEFT Contents: (
Token: SYMBOL Contents: two
Token: SPACE Contents:
Token: INT Contents: 456
Token: SPACE Contents:
Token: FLOAT Contents: -43.2
Token: SPACE Contents:
Token: QUOTED-STRING Contents: " \" quoted"
Token: SPACE Contents:
Token: RIGHT Contents: )
Token: RIGHT Contents: )
Andere Tipps
Es kann zu viel des Guten, aber einen Blick auf Irony auf CodePlex.
Irony ist ein Entwicklungs-Kit für Sprachen auf .NET-Plattform zu implementieren. Es nutzt die Flexibilität und Leistung von c # und .NET Framework 3.5 eine völlig neue und optimierte Technologie des Übersetzerbaus zu implementieren. Im Gegensatz zu den meisten bestehenden yacc / lex-Stil Lösungen Irony beschäftigen keinen Scanner oder Parser Code-Generierung aus Grammatikspezifikationen geschrieben in einer spezialisierten Metasprache. In Irony wird das Zielsprachgrammatik direkt in C # Operator Überlastungen kodiert Grammar Konstrukte zu exprimieren. Irony Scanner und Parser-Module verwenden, um die Grammatik als c # Klasse codiert, um den Parsing-Prozess zu steuern. Siehe den Ausdruck Grammatik Probe für ein Beispiel von Grammatikdefinition in C # -Klasse, und dessen Verwendung in einem Arbeits Parser.
Wenn Sie eine sehr unkonventionelle Grammatik haben, würde ich stark empfehlen nicht, Ihren eigenen Lexer / Parser rollen.
ich in der Regel finden Lexer / Parser für C # sind wirklich fehlt. Allerdings kommt F # mit fslex und fsyacc, die man lernen kann, wie man verwendet in diesem Tutorial . Ich habe mehr Lexer / Parser in F # geschrieben und verwenden sie in C #, und es ist sehr einfach zu tun.
Ich nehme an es ist nicht wirklich eines armen Mannes Lexer / Parser, zu sehen, dass Sie eine völlig neue Sprache zu lernen, um zu beginnen, aber es ist ein Anfang.
Ändern meiner ursprünglichen Antwort.
Hier finden Sie aktuelle SharpTemplate die Parser für andere Syntax-Typen hat, z.
#foreach ($product in $Products)
<tr><td>$product.Name</td>
#if ($product.Stock > 0)
<td>In stock</td>
#else
<td>Backordered</td>
#end
</tr>
#end
Es verwendet reguläre Ausdrücke für jede Art von Token:
public class Velocity : SharpTemplateConfig
{
public Velocity()
{
AddToken(TemplateTokenType.ForEach, @"#(foreach|{foreach})\s+\(\s*(?<iterator>[a-z_][a-z0-9_]*)\s+in\s+(?<expr>.*?)\s*\)", true);
AddToken(TemplateTokenType.EndBlock, @"#(end|{end})", true);
AddToken(TemplateTokenType.If, @"#(if|{if})\s+\((?<expr>.*?)\s*\)", true);
AddToken(TemplateTokenType.ElseIf, @"#(elseif|{elseif})\s+\((?<expr>.*?)\s*\)", true);
AddToken(TemplateTokenType.Else, @"#(else|{else})", true);
AddToken(TemplateTokenType.Expression, @"\${(?<expr>.*?)}", false);
AddToken(TemplateTokenType.Expression, @"\$(?<expr>[a-zA-Z_][a-zA-Z0-9_\.@]*?)(?![a-zA-Z0-9_\.@])", false);
}
}
, die wie folgt verwendet wird
foreach (Match match in regex.Matches(inputString))
{
...
switch (tokenMatch.TokenType)
{
case TemplateTokenType.Expression:
{
currentNode.Add(new ExpressionNode(tokenMatch));
}
break;
case TemplateTokenType.ForEach:
{
nodeStack.Push(currentNode);
currentNode = currentNode.Add(new ForEachNode(tokenMatch));
}
break;
....
}
....
}
Es drückt und Pop aus einem Stapel Zustand zu halten.
Malcolm Crowe eine große LEX / YACC Implementierung für C # hat hier . Werke von regulären Ausdrücken für die LEX ... und
Es ist möglich, Flex und Bison für C # zu verwenden.
Ein Forscher an der University of Ireland hat eine teilweise Umsetzung entwickelt, die unter folgendem Link zu finden sind: Flex / Bison für C #
Es könnte auf jeden Fall ein ‚armen mans Lexer‘ betrachtet werden, da er einige Probleme mit seiner Umsetzung, wie sie kein Prä-Prozessor, Probleme mit einem ‚baumelnden sonst‘ Fall noch haben scheint, etc.
Wenn Sie einen Blick auf die ExpressionConverter in meinem WPF Converters Bibliothek , hat es grundlegende lexing und Parsen von C # Ausdrücke. Keine Regex beteiligt ist, aus dem Speicher.
