Ho un'applicazione che ha bisogno di consentire agli utenti di scrivere espressioni simili a eccellere:Scrivi minilinguaggio
(H1 + (D1/C3)) * I8
e più complesse le cose come
Se (H1 = 'True', D3 * .2, D3 * .5)
Posso solo fare molto con le espressioni regolari. Qualche suggerimento sull'approccio giusto per fare questo e tutte le risorse che posso imparare saranno molto apprezzate.
Grazie!
Qualche altra domanda, troverete suggerimenti in:
Buona fortuna!
Ho un contro-esempio di come non per farlo: Will o’ the Wisp (poiché questo è il mio codice mi sento sicuro di criticarlo).
Che cos'è buono sul codice?
Cosa c'è di male circa il codice?
I leggere nel libro Modelli di progettazione il modello dell'interprete dovrebbe essere usato con cura. Quindi, sei d'accordo? – OscarRyz
Non ricordo quel passaggio da GoF e sfortunatamente ho prestato la mia copia ad un amico quindi non posso controllare ora. In realtà mi piace lo schema perché è facile e potente. D'altra parte, usato senza cura può comportare un sovraccarico, vedi il mio esempio di progetto. ;-) –
Date un'occhiata a questo progetto open source:
di fronte ad una situazione simile - la necessità di gestire brevi espressioni di una sola riga - ho scritto un parser. Le espressioni erano la logica booleana, nella forma
n1 = y and n2 > z
n2 != x or (n3 > y and n4 = z)
e così via. In inglese si potrebbe dire che ci sono atomi uniti da AND e OR, e ogni atomo ha tre elementi: un attributo sul lato sinistro, un operatore e un valore. Perché era così succinta che penso che l'analisi fosse più facile. L'insieme dei possibili attributi è noto e limitato (ad esempio: nome, dimensione, tempo).Gli operatori variano in base agli attributi: attributi diversi richiedono set di operatori diversi. E la gamma e il formato dei valori possibili variano a seconda dell'attributo.
Per analizzare, ho diviso la stringa su spazio vuoto usando String.Split(). In seguito mi sono reso conto che prima di Split(), avevo bisogno di normalizzare la stringa di input, inserendo spazi bianchi prima e dopo il paren. L'ho fatto con una regex.Replace().
L'output della divisione è una serie di token. Quindi l'analisi si verifica in un ciclo di grandi dimensioni con un interruttore sul valore dell'attributo sul lato sinistro. Con ogni giro del ciclo, ero pronto a borbottare in un gruppo di gettoni. Se il primo token era un open paren, allora il gruppo era solo un token di lunghezza: il paren stesso. Per i token che erano nomi noti - i miei valori di attributo - il parser doveva borbottare in un gruppo di 3 token, uno per nome, operatore e valore. Se in qualsiasi momento non ci sono abbastanza token, il parser genera un'eccezione. Basato sul flusso di token, lo stato del parser cambierebbe. Una congiunzione (AND, OR, XOR) significava spingere l'atomo precedente su una pila, e quando l'atomo successivo era finito, io avrei fatto scoppiare l'atomo precedente e unire quei due atomi in un atomo composto. E così via. La gestione dello stato si è verificata alla fine di ogni ciclo del parser.
Atom current;
for (int i=0; i < tokens.Length; i++)
{
switch (tokens[i].ToLower())
{
case "name":
if (tokens.Length <= i + 2)
throw new ArgumentException();
Comparison o = (Comparison) EnumUtil.Parse(typeof(Comparison), tokens[i+1]);
current = new NameAtom { Operator = o, Value = tokens[i+2] };
i+=2;
stateStack.Push(ParseState.AtomDone);
break;
case "and":
case "or":
if (tokens.Length <= i + 3)
throw new ArgumentException();
pendingConjunction = (LogicalConjunction)Enum.Parse(typeof(LogicalConjunction), tokens[i].ToUpper());
current = new CompoundAtom { Left = current, Right = null, Conjunction = pendingConjunction };
atomStack.Push(current);
break;
case "(":
state = stateStack.Peek();
if (state != ParseState.Start && state != ParseState.ConjunctionPending && state != ParseState.OpenParen)
throw new ArgumentException();
if (tokens.Length <= i + 4)
throw new ArgumentException();
stateStack.Push(ParseState.OpenParen);
break;
case ")":
state = stateStack.Pop();
if (stateStack.Peek() != ParseState.OpenParen)
throw new ArgumentException();
stateStack.Pop();
stateStack.Push(ParseState.AtomDone);
break;
// more like that...
case "":
// do nothing in the case of whitespace
break;
default:
throw new ArgumentException(tokens[i]);
}
// insert housekeeping for parse states here
}
Questo è semplificato, solo un po '. Ma l'idea è che ogni dichiarazione del caso è abbastanza semplice. È facile analizzare in un'unità atomica dell'espressione. La parte difficile era unirli tutti insieme in modo appropriato.
Questo trucco è stato eseguito nella sezione di pulizia, alla fine di ogni loop di slurp, utilizzando la pila di stati e la pila di atomi. Cose diverse possono accadere in base allo stato del parser. Come ho detto, in ogni dichiarazione di caso, lo stato del parser potrebbe cambiare, con lo stato precedente essere spinto su una pila. Poi alla fine dell'istruzione switch, se lo stato diceva che avevo appena finito di analizzare un atomo e c'era una congiunzione in sospeso, avrei spostato l'atomo appena analizzato nel CompoundAtom. Il codice è simile al seguente:
state = stateStack.Peek();
if (state == ParseState.AtomDone)
{
stateStack.Pop();
if (stateStack.Peek() == ParseState.ConjunctionPending)
{
while (stateStack.Peek() == ParseState.ConjunctionPending)
{
var cc = critStack.Pop() as CompoundAtom;
cc.Right = current;
current = cc; // mark the parent as current (walk up the tree)
stateStack.Pop(); // the conjunction is no longer pending
state = stateStack.Pop();
if (state != ParseState.AtomDone)
throw new ArgumentException();
}
}
else stateStack.Push(ParseState.AtomDone);
}
Un altro po 'di magia era EnumUtil.Parse. Ciò mi consente di analizzare cose come "<" in un valore enum. Si supponga di definire le enumerazioni in questo modo:
internal enum Operator
{
[Description(">")] GreaterThan,
[Description(">=")] GreaterThanOrEqualTo,
[Description("<")] LesserThan,
[Description("<=")] LesserThanOrEqualTo,
[Description("=")] EqualTo,
[Description("!=")] NotEqualTo
}
Normalmente Enum.Parse cerca il nome simbolico del valore enum, e < non è un nome simbolico valido. EnumUtil.Parse() cerca la cosa nella descrizione. Il codice è simile al seguente:
internal sealed class EnumUtil
{
/// <summary>
/// Returns the value of the DescriptionAttribute if the specified Enum value has one.
/// If not, returns the ToString() representation of the Enum value.
/// </summary>
/// <param name="value">The Enum to get the description for</param>
/// <returns></returns>
internal static string GetDescription(System.Enum value)
{
FieldInfo fi = value.GetType().GetField(value.ToString());
var attributes = (DescriptionAttribute[])fi.GetCustomAttributes(typeof(DescriptionAttribute), false);
if (attributes.Length > 0)
return attributes[0].Description;
else
return value.ToString();
}
/// <summary>
/// Converts the string representation of the name or numeric value of one or more enumerated constants to an equivilant enumerated object.
/// Note: Utilised the DescriptionAttribute for values that use it.
/// </summary>
/// <param name="enumType">The System.Type of the enumeration.</param>
/// <param name="value">A string containing the name or value to convert.</param>
/// <returns></returns>
internal static object Parse(Type enumType, string value)
{
return Parse(enumType, value, false);
}
/// <summary>
/// Converts the string representation of the name or numeric value of one or more enumerated constants to an equivilant enumerated object.
/// A parameter specified whether the operation is case-sensitive.
/// Note: Utilised the DescriptionAttribute for values that use it.
/// </summary>
/// <param name="enumType">The System.Type of the enumeration.</param>
/// <param name="value">A string containing the name or value to convert.</param>
/// <param name="ignoreCase">Whether the operation is case-sensitive or not.</param>
/// <returns></returns>
internal static object Parse(Type enumType, string stringValue, bool ignoreCase)
{
if (ignoreCase)
stringValue = stringValue.ToLower();
foreach (System.Enum enumVal in System.Enum.GetValues(enumType))
{
string description = GetDescription(enumVal);
if (ignoreCase)
description = description.ToLower();
if (description == stringValue)
return enumVal;
}
return System.Enum.Parse(enumType, stringValue, ignoreCase);
}
}
Ho ricevuto quella cosa EnumUtil.Parse() da un'altra parte. Forse qui?
È possibile utilizzare il compilatore JScript .NET o interfaccia con IronPython, IronRuby o IronScheme (denominato alfabeticamente, non preferenza; p).
Un parser ricorsivo-discendente è perfetto per questo. Probabilmente non hai nemmeno bisogno di costruire un albero di analisi: puoi fare la valutazione mentre analizzi.
/* here's a teeny one in C++ */
void ScanWhite(const char* &p){
while (*p==' ') p++;
}
bool ParseNum(const char* &p, double &v){
ScanWhite(p);
if (!DIGIT(*p)) return false;
const char* p0 = p;
while(DIGIT(*p)) p++;
if (*p == '.'){
p++;
while(DIGIT(*p)) p++;
}
v = /* value of characters p0 up to p */;
return true;
}
bool ParseId(const char* &p, double &v){
ScanWhite(p);
if (ALPHA(p[0]) && DIGIT(p[1])){
v = /* value of cell whose name is p[0], p[1] */;
p += 2;
return true;
}
return false;
}
bool ParseChar(const char* &p, char c){
ScanWhite(p);
if (*p != c) return false;
p++;
return true;
}
void ParseExpr(const char* &p, double &v); /* forward declaration */
void ParsePrimitive(const char* &p, double &v){
if (ParseNum(p, v));
else if (ParseId(p, v));
else if (ParseChar(p, '(')){
ParseExpr(p, v);
if (!ParseChar(p, ')'){/* throw syntax error */}
}
else {/* throw syntax error */}
}
#define PARSE_HIGHER ParsePrimitive
void ParseUnary(const char* &p, double &v){
if (ParseChar(p, '-')){
ParseUnary(p, v);
v = -v;
}
else {
PARSE_HIGHER(p, v);
}
}
#undef PARSE_HIGHER
#define PARSE_HIGHER ParseUnary
void ParseProduct(const char* &p, double &v){
double v2;
PARSE_HIGHER(p, v);
while(true){
if (ParseChar(p, '*')){
PARSE_HIGHER(p, v2);
v *= v2;
}
else if (ParseChar(p, '/')){
PARSE_HIGHER(p, v2);
v /= v2;
}
else break;
}
}
#undef PARSE_HIGHER
#define PARSE_HIGHER ParseProduct
void ParseSum(const char* &p, double &v){
double v2;
PARSE_HIGHER(p, v);
while(true){
if (ParseChar(p, '+')){
PARSE_HIGHER(p, v2);
v += v2;
}
else if (ParseChar(p, '-')){
PARSE_HIGHER(p, v2);
v -= v2;
}
else break;
}
}
#undef PARSE_HIGHER
#define PARSE_HIGHER ParseSum
void ParseExpr(const char* &p, double &v){
PARSE_HIGHER(p, v);
}
double ParseTopLevel(const char* buf){
const char* p = buf;
double v;
ParseExpr(p, v);
return v;
}
Ora, se si chiama ParseTop, verrà calcolato il valore di un'espressione per te.
La ragione della macro PARSE_HIGHER è semplificare l'aggiunta di operatori a livelli intermedi di precedenza.
Fare l'istruzione "se" è un po 'più complicato.Ogni routine di analisi richiede un ulteriore argomento di "abilitazione", quindi non esegue alcun calcolo a meno che non sia abilitato. Quindi si analizza la parola "if", si analizza l'espressione di test e quindi si analizzano le due espressioni di risultato, con l'inattivo disattivato.
Check out ANTLR. Definisci una sintassi del linguaggio, testala usando uno strumento GUI e generi codice sorgente in una varietà di lingue. Open Source.
Consiglierei contro ANTLR per progetti molto piccoli in quanto è uno strumento molto pesante che produce parser molto sofisticati che, a loro volta, sono molto pesanti. –
Anche se non si utilizza ANTLR per produrre il parser, è uno strumento eccellente per aiutare a definire e testare una grammatica. Mi affido a cose molto semplici, ma penso di conoscere molte delle trappole (come sono caduto nella maggior parte di esse :-()) Per cose complesse è un gioco da ragazzi –
Vorrei raccomandare il libro Constructing Little Languages. Ti guida attraverso molte nozioni di base sul compilatore necessarie per completare correttamente questa attività.
Hai evidenziato il fatto che le espressioni regolari non funzioneranno se non hai limiti rigorosi sulla tua lingua. Come altri hanno già detto, uno Recursive Descent Parser farà il trucco.
La scelta successiva sarebbe se utilizzare un Parser Generator come ANTLR o per scriverne uno da zero.
vi consiglio di guardare CoreCalc lavoro/FunCalc: http://www.itu.dk/people/sestoft/funcalc/
Ho usato la loro grammatica per generatore di parser COCO \ R nella produzione e funziona veramente veloce.
Tutto quello che dovete fare è: 1. get eccellere grammatica da corecalc coco.exe 2. eseguire su di esso (genera parser per le espressioni Excel-like) 3. tradurre albero di espressione di notazione polacca inversa 4. semplice calc
Vuoi compilare il codice per il CLR? Sembra un obiettivo ragionevole per una DSL. – MSalters
Questo è un compito abbastanza difficile (per interpretare questi tipi di funzioni). Targeting del CLR non renderà tutto più semplice ... –
possibile duplicato di [Imparare a scrivere un compilatore] (http://stackoverflow.com/questions/1669/learning-to-write-a-compiler) –