Tôi có một ứng dụng mà cần phải cho phép người dùng viết các biểu thức tương tự như nổi trội:Viết một mini-ngôn ngữ
(H1 + (D1/C3)) * I8
và phức tạp hơn những thứ như
Nếu (H1 = 'Đúng', D3 * .2, D3 * .5)
Tôi chỉ có thể thực hiện rất nhiều với cụm từ thông dụng. Bất kỳ đề xuất nào về cách tiếp cận đúng để thực hiện điều này cũng như bất kỳ tài nguyên nào tôi có thể học hỏi sẽ được đánh giá cao.
Cảm ơn!
Một số câu hỏi khác, bạn sẽ tìm thấy những gợi ý trong:
Chúc may mắn!
Tôi đã có ví dụ về cách không để làm điều đó: Will o’ the Wisp (vì đây là mã của riêng tôi, tôi cảm thấy tự tin khi chỉ trích nó).
Có gì tốt về mã?
xấu về mã là gì?
I đọc trong các mẫu thiết kế mẫu mô hình thông dịch nên được sử dụng cẩn thận. Vì vậy, bạn có đồng ý về điều đó không? – OscarRyz
Tôi không nhớ đoạn văn đó từ GoF và tiếc là tôi đã mượn bản sao của mình cho một người bạn để tôi không thể kiểm tra ngay bây giờ. Tôi thực sự thích mô hình vì nó dễ dàng và mạnh mẽ. Mặt khác, được sử dụng mà không cần chăm sóc nó có thể phải chịu khá một chi phí, xem dự án ví dụ của tôi. ;-) –
Có xem xét dự án mã nguồn mở này:
Khi đối mặt với một tình huống tương tự - sự cần thiết phải xử lý các biểu một dòng ngắn - Tôi đã viết một phân tích cú pháp. Các biểu thức là logic boolean, của biểu mẫu
n1 = y and n2 > z
n2 != x or (n3 > y and n4 = z)
v.v. Trong tiếng Anh, bạn có thể nói rằng có các nguyên tử được nối với AND và OR, và mỗi nguyên tử có ba phần tử - một thuộc tính bên trái, một toán tử và một giá trị. Bởi vì nó đã rất succint tôi nghĩ rằng việc phân tích cú pháp được dễ dàng hơn. Tập hợp các thuộc tính có thể được biết và giới hạn (ví dụ: tên, kích thước, thời gian).Các toán tử thay đổi theo thuộc tính: các thuộc tính khác nhau lấy các toán tử khác nhau. Và phạm vi và định dạng của các giá trị có thể khác nhau tùy theo thuộc tính.
Để phân tích cú pháp, tôi chia chuỗi trên khoảng trắng bằng cách sử dụng String.Split(). Sau này tôi nhận ra rằng trước khi Split(), tôi cần phải bình thường hóa chuỗi đầu vào - chèn khoảng trắng trước và sau khi parens. Tôi đã làm điều đó với một regex.Replace().
Đầu ra của phần tách là một mảng mã thông báo. Sau đó phân tích cú pháp xảy ra trong một vòng lặp lớn với một công tắc trên giá trị thuộc tính bên trái. Với mỗi vòng lặp của vòng lặp, tôi đã được thiết lập để slurp trong một nhóm các thẻ. Nếu mã thông báo đầu tiên là một paren mở, thì nhóm chỉ dài một mã thông báo: chính là paren. Đối với các mã thông báo là các tên nổi tiếng - các giá trị thuộc tính của tôi - trình phân tích cú pháp phải ẩn trong một nhóm gồm 3 thẻ, mỗi mã cho tên, toán tử và giá trị. Nếu tại bất kỳ điểm nào không có đủ mã thông báo, trình phân tích cú pháp sẽ đưa ra một ngoại lệ. Dựa trên luồng mã thông báo, trạng thái phân tích cú pháp sẽ thay đổi. Một kết hợp (AND, OR, XOR) có nghĩa là đẩy nguyên tử trước vào một chồng, và khi nguyên tử tiếp theo được hoàn thành, tôi sẽ bật nguyên tử trước đó và nối hai nguyên tử đó thành một nguyên tử phức hợp. Và cứ thế. Việc quản lý nhà nước xảy ra ở cuối mỗi vòng lặp của trình phân tích cú pháp.
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
}
Đơn giản hóa, chỉ một chút. Nhưng ý tưởng là mỗi tuyên bố trường hợp khá đơn giản. Thật dễ dàng để phân tích cú pháp trong một đơn vị nguyên tử của biểu thức. Phần khó khăn đã được tham gia tất cả cùng nhau một cách thích hợp.
Bí quyết đó được thực hiện trong phần bảo trì, ở cuối mỗi vòng lặp slurp, sử dụng ngăn xếp trạng thái và ngăn xếp nguyên tử. Các công cụ khác nhau có thể xảy ra theo trạng thái phân tích cú pháp. Như tôi đã nói, trong mỗi tuyên bố trường hợp, trạng thái phân tích cú pháp có thể thay đổi, với trạng thái trước đó bị đẩy lên một chồng. Sau đó, ở cuối báo cáo chuyển đổi, nếu tiểu bang cho biết tôi vừa hoàn thành phân tích cú pháp một nguyên tử và có một kết hợp đang chờ xử lý, tôi sẽ chuyển nguyên tử vừa được phân tích cú pháp vào CompoundAtom. Mã trông giống như sau:
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);
}
Một chút ma thuật khác là EnumUtil.Parse. Điều đó cho phép tôi phân tích cú pháp những thứ như "<" thành giá trị enum. Giả sử bạn xác định sự đếm của bạn như thế này:
internal enum Operator
{
[Description(">")] GreaterThan,
[Description(">=")] GreaterThanOrEqualTo,
[Description("<")] LesserThan,
[Description("<=")] LesserThanOrEqualTo,
[Description("=")] EqualTo,
[Description("!=")] NotEqualTo
}
thường Enum.Parse tìm kiếm tên mang tính biểu tượng của giá trị enum, và < không phải là một tên mang tính biểu tượng hợp lệ. EnumUtil.Parse() tìm kiếm điều trong phần mô tả. Mã trông giống như sau:
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);
}
}
Tôi nhận được điều EnumUtil.Parse() từ một nơi khác. Có lẽ là ở đây?
Bạn có thể sử dụng trình biên dịch .NET JScript hoặc giao diện với IronPython, IronRuby hoặc IronScheme (được đặt tên theo thứ tự abc, không ưu tiên; p).
Trình phân tích cú pháp đệ quy nhỏ là hoàn hảo cho việc này. Có thể bạn thậm chí không phải xây dựng một cây phân tích - bạn có thể thực hiện đánh giá khi phân tích cú pháp.
/* 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;
}
Bây giờ nếu bạn chỉ cần gọi ParseTop, nó sẽ tính giá trị của biểu thức cho bạn.
Lý do cho macro PARSE_HIGHER là giúp dễ dàng thêm các toán tử ở cấp ưu tiên trung gian.
Để thực hiện câu lệnh "if" có liên quan nhiều hơn một chút.Mỗi thói quen phân tích cú pháp cần một đối số "bật" bổ sung, do đó, nó không tính toán trừ khi được bật. Sau đó, bạn phân tích cú pháp từ "if", phân tích cú pháp biểu thức kiểm tra và sau đó phân tích cú pháp hai biểu thức kết quả, với biểu thức kết quả không hoạt động bị vô hiệu hóa.
Kiểm tra ANTLR. Bạn định nghĩa một cú pháp ngôn ngữ, kiểm tra nó bằng cách sử dụng một công cụ GUI và tạo mã nguồn bằng nhiều ngôn ngữ. Mã nguồn mở.
Tôi sẽ tư vấn chống lại ANTLR cho các dự án rất nhỏ vì nó là một công cụ có trọng lượng rất nặng tạo ra các trình phân tích cú pháp rất tinh vi, bản thân chúng rất nặng. –
Thậm chí nếu bạn không sử dụng ANTLR để tạo trình phân tích cú pháp, nó là một công cụ tuyệt vời để giúp xác định và kiểm tra ngữ pháp. Tôi handcrank công cụ rất đơn giản, nhưng tôi nghĩ rằng tôi biết nhiều bẫy (như tôi đã rơi vào hầu hết trong số họ :-()) Đối với công cụ phức tạp nó là một bon-brainer –
Tôi muốn giới thiệu sách Constructing Little Languages. Nó sẽ đưa bạn qua nhiều điều cơ bản về trình biên dịch cần thiết để hoàn thành nhiệm vụ này đúng cách.
Bạn đã đưa ra thực tế là cụm từ thông dụng sẽ không hoạt động trừ khi bạn có một số giới hạn nghiêm ngặt về ngôn ngữ của mình. Giống như những người khác đã nói, một Recursive Descent Parser sẽ thực hiện thủ thuật.
Lựa chọn tiếp theo sẽ là sử dụng Parser Generator như ANTLR hoặc để viết một từ đầu.
Tôi khuyên bạn nên nhìn vào CoreCalc việc/FunCalc: http://www.itu.dk/people/sestoft/funcalc/
Tôi đã sử dụng ngữ pháp của họ cho máy phát điện phân tích cú pháp COCO \ R trong sản xuất và nó hoạt động rất nhanh.
Tất cả bạn cần làm là: 1. get trội ngữ pháp từ corecalc 2. chạy coco.exe vào nó (tạo phân tích cú pháp cho các biểu thức excel-like) 3. dịch cây biểu thức để đảo ngược Kí pháp Ba Lan 4. đơn giản calc
Bạn có muốn biên dịch mã cho CLR không? Điều đó có vẻ là một mục tiêu hợp lý cho một DSL. – MSalters
Đây là một nhiệm vụ khó khăn (để giải thích các loại chức năng đó). Nhắm mục tiêu CLR không nhất thiết phải làm cho nó dễ dàng hơn ... –
bản sao có thể có của [Học viết một trình biên dịch] (http://stackoverflow.com/questions/1669/learning-to-write-a-compiler) –