كيف أقوس تعبير برمجيا؟

Question

لدي فكرة عن برنامج بسيط لتقديمه من شأنه أن يساعدني في أسبقية المشغل بلغات مثل C. الجزء الأكثر صعوبة من هذا هو قوسين التعبير. على سبيل المثال، أريد هذا:

*a.x++ = *b.x++

تحويلها إلى هذا:

((*(((a).(x))++)) = (*(((b).(x))++)))

التي قمت بها يدويا في هذه الخطوات:

           *a.x++ = *b.x++
       *(a).(x)++ = *(b).(x)++
     *((a).(x))++ = *((b).(x))++
   *(((a).(x))++) = *(((b).(x))++)
 (*(((a).(x))++)) = (*(((b).(x))++))
((*(((a).(x))++)) = (*(((b).(x))++)))

ما هي أفضل طريقة لإنجاز هذا برمجيا؟ هل هناك بالفعل حل هناك أنه يمكنني استخدامه؟ أفضل أن أفعل ذلك في إما PHP أو C أو C ++ أو PYTHON أو RUBY.

(هذه ليست الفكرة برمتها لبرنامجي، إنها الخطوة الأولى فقط.)

Answer 1

ما عليك سوى التقاط محلل لغتك المختارة، على سبيل المثال ج المحلل, تحليل التعبير / التعليمات البرمجية المصدر وطباعة AST مرة أخرى بالطريقة التي تريدها.

test.c:

void main(void){
    int c = 2;
}

طرفية:

$ python
>>> import pycparser
>>> test = pycparser.parse_file('test.c')
>>> test.show()
FileAST: 
  FuncDef: 
    Decl: main, [], []
      FuncDecl: 
        ParamList: 
          Typename: []
            TypeDecl: None, []
              IdentifierType: ['void']
        TypeDecl: main, []
          IdentifierType: ['void']
    Compound: 
      Decl: c, [], []
        TypeDecl: c, []
          IdentifierType: ['int']
        Constant: int, 2
>>> for node in test.ext:
...     print node
...
<pycparser.c_ast.FuncDef object at 0x7fe1436db750>
>>>

Answer 2

ستحتاج إلى محلل من نوع ما يفهم العمق للمشغل. النسخة المعتادة ل C هي Lexx / YACC أو Flex / Bison، وأسهل طريقة للقيام بها هي بناء شجرة تحليل. بمجرد القيام بذلك، فقط امشي شجرة التحليل في طلب "Preorder" و EMIT Parens كما تدخل وترك عقدة.

Answer 3

الطريقة الأكثر موثوقية ستكون تحليل التعبير (أخذا بالإعتبار قواعد الأسبقية, بالطبع)، ثم قم بمعالجة AST الناتجة (شجرة بناء الجملة مجردة) بطريقة من أعلى إلى أسفل، إضافة قوسين أثناء التحرك

Answer 4

ماذا عن التحويل إلى postfix والتقييم. يمكنك محاولة إذا كان النهج التالي يعمل. يتيح أخذ * A.x ++

Operator    Precedence  Arguments Needed
.           3               2
++          2               1
*           1               1

الآن تحويل التعبير إلى تدوين postfix. هذا يجب أن يعطيك

a x . ++ *

الآن تقييم Postfix بسيط مثل دفع الأشياء إلى كومة، عندما تضغط على أحد المشغل، يقوم بتبول من عناصر Top n (حسب الحاجة حسب المشغل) وأرسلها كوسائط، ويعيد تخزين النتائج إلى المكدس. في حالتك، بدلا من التقييم، سترجع تمثيل نصي للعمل

        Stack
Read a      a
Read x      x
Read .      (a.x)
Read ++     ((a.x)++)
Read *      (*((a.x)++))

إذا كان ذلك يساعد، فقد ترغب في إلقاء نظرة على:
http://www.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/
BART DE SMET's DYNCALC سلسلة من المشاركات
محاولتي في tdding حل مماثل

Answer 5

يمكنك إنشاء شجرة تعبير ثنائية من المشغلين.

أعتقد أن هناك العديد من الخوارزميات المتاحة عبر الإنترنت لإنشاء هذه الشجرة بالفعل.

طريقة بسيطة يمكن أن أفكر فيها، هي عن طريق فرز المشغل بالأبق الأسبقية، ثم قم بتقسيم السلسلة إلى قسمين من قبل المشغل بأقل الأسباب أولا، ثم استمر بشكل متكرر في تقسيم الجزءان الآخرين الآخرين وأكثر من ذلك، ثم في النهاية، أنت في النهاية سوف يكون التعبير في شكل شجرة ثنائية.

ثم عندما يكون لديك التعبير في شكل شجرة ثنائية، يمكنك بعد ذلك "قوسين" لأعلى من مغادرة الشجرة إلى الجذر.

وبالطبع، يمكنك ترجمة المحللين الكاملين عبر YACC / BISON.

Answer 6

كمثال بسيط:

Exp = Term | Exp, AddOp, Term 
Term = Factor | Term, MulOp, Factor
Factor = Number | Ident | PreOp, Factor | (, Exp, ) | Factor, PostOp

يمكنك استخدام Grammar لكتابة الترجمات:

Exp    = Term                    -> Term
       | Exp, AddOp, Term        -> (, Exp, AddOp, Term, )
Term   = Factor                  -> Factor
       | Term, MulOp, Factor     -> (, Term, MulOp, Factor, )
Factor = Number                  -> Number
       | Ident                   -> Ident
       | PreOp, Factor           -> (, PreOp, Factor, )
       | (, Exp, )               -> (, Exp, )
       | Factor, PostOp          -> (, Factor, PostOp, )

في أي حالة:

a-- + b * (a+b) 

يترجم إلى:

((a--) + (b * ((a+b))))

Answer 7

التحليل هو موضوع ضخم. نظرا لأنك تريد فقط استخدامه لحل مشكلة محددة، فحاول عدم مغمورة في جميع خوارزميات التحليل المحددة التي يقترحها الناس. بدلا من ذلك، هناك العديد من مولدات المحلل المحللين، مثل قرن الوعل أو Bison التي، بالنظر إلى قواعد اللغة المناسبة، ستتحليل النص والسماح لك بإجراء عمليات برنامجية على المكونات - مثل وضع الأقواس المحيطة بهم. بعض هذه الأنظمة تأتي مع قواعد النحوية ل C، أو لديك مثل هذا النحو المتاحة.

يمكن أن تولد Antlr المحللين في أي من اللغات التي ذكرتها؛ يرى http://www.antlr.org/

Answer 8

يمكنك العثور على "CPAREN" في أرشيف NET NET.Sources مجموعة أخبار.

إذا كنت تبحث عن "Google) ل" cparen "، فستحصل على الكثير من الضوضاء، ولكن إذا كنت تبحث عن Net.Sources و" cparen.c "الذي يضيق البحث بما يكفي ليكون مفيدا.

هنا موقع واحد:

http://www.megalextoria.com/usenet-archive/news005f3/b14/net/sources/00000360.html.

انها ليست أرشيف شل، كما كنت أتوقع. يبدو وكأنه ملف القطران نص نقي ASCII. هناك عدد قليل من الملفات التي يمكنك فكها فقط باليد.

Answer 9

كتبت برنامجا في بيثون إلى قوس سلسلة تعبير.

def pref(op):
    print "called with op", op
    ret = -1
    if op == '+':
        print "matched +"
        ret = 1
    if op == '-':
        print "matched -"
        ret = 2
    if op == '*':
        print "matched *"
        ret = 3
    if op == '/':
        print "matched /"
        ret = 4

    return ret

def evaluate(expr, operand_stack, operator_stack):
    print "**In evaluate**"
    print operator_stack
    print operand_stack

    expr1 = operand_stack.pop()
    expr2 = operand_stack.pop()
    op    = operator_stack.pop()

    # Parenthesize the expression
    expr = "(" + expr2 + op + expr1 + ")"
    print "expr1", expr1
    print "expr2", expr2
    print "expr", expr

    # Push the result back on the stack
    operand_stack.append(expr)

    print operator_stack
    print operand_stack
    print "**Out evaluate**"
    return expr

def looper(str, expr, operator_stack, operand_stack):
    l = 0
    cnt = len(str)

    # Loop over the input string
    while  l < cnt:
        if str[l] in ('+', '-', '*', '/'):
            print "operator found: op, index", str[l], l
            print operator_stack, len(operator_stack)

            x = len(operator_stack) - 1
            if x > 0:
                print "Comparing:", operator_stack[x], str[l]

                # If op on stack has higher preference than the op in question
                if (pref(operator_stack[x]) > pref(str[l])):
                    expr = evaluate(expr, operand_stack, operator_stack)
            operator_stack.append(str[l])
        else:
            # Add the operand to operand stack
            operand_stack.append(str[l])
        l += 1

    print operator_stack
    print operand_stack

    print "Take care of last elements"
    op_cnt = len(operator_stack)
    while op_cnt:
        expr = evaluate(expr, operand_stack, operator_stack)
        op_cnt -= 1

    print operator_stack
    print operand_stack

if __name__ == '__main__':
    str = "a+c*d-e/w*x+a-s"
    cnt = len(str)

    operand_stack  = []
    operator_stack  = []
    expr = ""
    looper(str, expr, operator_stack, operand_stack)

    print "Output=>", operand_stack[0]

Answer 10

هناك برنامج مفتوح للغاية (الثمانينات من الثمانينات) للقيام بهذا بالضبط. يطلق عليه "CPAREN"، لكنني ملعون إذا استطعت أن أجدها على الشبكة. يذكر متحمس فقط منه، على سبيل المثالhttps://groups.google.com/group/comp.lang.c/tree/browse_frm/month/1990-03/1583B4728A6D94DB.http://www.language-c.info/re-should-i-capitalize-const-mentifiers.

إذا كان لديك حظ أكثر مني في العثور عليه، فالكتب