الترميز التكراري النموذجي
تحتاج هذه المقالة أو المقطع إلى مصادر إضافية لتحسين وثوقيتها. الرجاء المساعدة في تطوير هذه المقالة بإضافة استشهادات من مصادر موثوقة. المعلومات غير المنسوبة إلى مصدر يمكن التشكيك فيها وإزالتها. (ديسمبر 2017)
الترميز التكراري النموذجي ترميز من أعلى لأسفل، تمت صياغته من مجموعة من الخطوات ثنائية-التكرار (أو ما يعادلها من الخطوات غير المتكررة).[1][2] حيث عادة ما يقوم كل إجراء من هذه الإجراءات بتطبيق إحدى القواعد الإنتاجية للقواعد النحوية. وعلى هذا يكون شكل البرنامج الناتج قريب الشبه جدا من القواعد النحوية التي يتعرف عليها.
الترميز الخطي عبارة عن ترميز تكراري نموذجي لا يتطلب تراجع. والترميز الخطي ممكن فقط للترميز من أعلى لأسفل للنصوص التي تخلو من القواعد النحوية بمعنى أنها نصوص لا تتضمن قواعد نحوية والتي لابد لها من بعض الأرقام الموجبة k والتي تسمح للترميز التكراري النموذجي بتحديد الناتج الذي يستخدمه وذلك بفحص رموز الأرقام الموجبة k التالية للمدخلات. (وعلى هذا فإن النصوص الخالية من القواعد النحوية تستبعد كل القواعد النحوية المبهمة وكذلك كل القواعد النحوية التي تحتوي على ترميز أيسر. يمكن تحويل النصوص الخالية من القواعد النحوية إلى قواعد نحوية بديلة لا تحتوي على تكرار أيسر إلا أن إزالة التكرار الأيسر لا يؤدي دائما إلى نصوص تخلو من القواعد النحوية). بعمل الترميز الخطي في توقيت خطي.
التكرار النموذجي بملفات احتياطية طريقة تحدد النواتج التي تستخدم بتجربة كل ناتج وراء الآخر. والتكرار النموذجي بملفات احتياطية ليس قاصرا على النصوص الخالية من القواعد النحوية ولكن ليس مضمونا أن ينتهي ما لم تكن القواعد النحوية غير مستخدمة. والترميز الذي يستخدم تكرار نموذجي بملفات احتياطية قد يتطلب زمن أُسي.
ورغم استخدام الترميز الخطي على نطاق واسع يفضل المبرمجون إنشاء ترميز من اليسار لليمين أو ترميز مباشر من اليسار لليمين من خلال أدوات الترميز بدون تحويل القواعد النحوية إلى صيغة تخلو من القواعد
محتويات
1 مثال على الترميز
1.1 استخدام لغة C للبرمجة
2 البناء في لغات البرمجة الوظيفية
3 انظر أيضا
4 مراجع
5 وصلات خارجية
مثال على الترميز
صيغة ENBF الشبيهة بالقواعد النحوية (للغة البرمجة PL/0 لنيكولاس ريث من Algorithms+ تركيب البيانات = البرامج) وتكون بصيغة LL(1):
program = block ".".
block =
["const" ident "=" number {"," ident "=" number} ";"]
["var" ident {"," ident} ";"]
{"procedure" ident ";" block ";"} statement.
statement =
[ident ":=" expression
| "call" ident
| "begin" statement {";" statement} "end"
| "if" condition "then" statement
| "while" condition "do" statement
].
condition =
"odd" expression
| expression ("="|"#"|"<"|"<="|">"|">=") expression.
expression = ["+"|"-"] term {("+"|"-") term}.
term = factor {("*"|"/") factor}.
factor =
ident
| number
| "(" expression ")".
يمكن التعبير عن رموز الأحرف باستخدام الأعداد. يمكن تحديد كل رمز لا يحتوي على أحرف من خلال قاعدة من القواعد النحوية باستثناء الرموز والأرقام، والتي يفترض تعريفها ضمنيا
استخدام لغة C للبرمجة
بعد ذلك يأتي استخدام الترميز النموذجي التكراري للغة السابقة بلغة البرمجة سي C. إذا تمت قراءة الترميز في الترميز الأصلي وينتج عنه رسالة خطأ. في حالة عدم تمكن الكود من الترميز يخرج في صمت إذا تم ترميز الكود بشكل صحيح.
لاحظ مدى التشابه الكبير بين الترميز الخطي في الأسفل مع القواعد النحوية في الأعلى. هناك إجراء لكل رمز غير خطي في القواعد. تترتب الرموز بطريقة الترتيب من أعلى لأسفل حتى تتم معالجة آخر رمز غير خطي. تعتمد أجزاء البرنامج على متغير عالمي هو sym، يحتوي على الجيل الثاني من رموز المدخلات ودالة getsym والتي تعمل على تحديث النظام عند استدعائها.
تم حذف تطبيقات دوال getsym والأخطاء للتبسيط
typedef enum {ident, number, lparen, rparen, times, slash, plus,
minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
varsym, procsym, period, oddsym} Symbol;
Symbol sym;
void getsym(void);
void error(const char msg);
void expression(void);
int accept(Symbol s) {
if (sym == s) {
getsym();
return 1;
}
return 0;
}
int expect(Symbol s) {
if (accept(s))
return 1;
error("expect: unexpected symbol");
return 0;
}
void factor(void) {
if (accept(ident)) {
;
} else if (accept(number)) {
;
} else if (accept(lparen)) {
expression();
expect(rparen);
} else {
error("factor: syntax error");
getsym();
}
}
void term(void) {
factor();
while (sym == times || sym == slash) {
getsym();
factor();
}
}
void expression(void) {
if (sym == plus || sym == minus)
getsym();
term();
while (sym == plus || sym == minus) {
getsym();
term();
}
}
void condition(void) {
if (accept(oddsym)) {
expression();
} else {
expression();
if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {
getsym();
expression();
} else {
error("condition: invalid operator");
getsym();
}
}
}
void statement(void) {
if (accept(ident)) {
expect(becomes);
expression();
} else if (accept(callsym)) {
expect(ident);
} else if (accept(beginsym)) {
do {
statement();
} while (accept(semicolon));
expect(endsym);
} else if (accept(ifsym)) {
condition();
expect(thensym);
statement();
} else if (accept(whilesym)) {
condition();
expect(dosym);
statement();
}
}
void block(void) {
if (accept(constsym)) {
do {
expect(ident);
expect(eql);
expect(number);
} while (accept(comma));
expect(semicolon);
}
if (accept(varsym)) {
do {
expect(ident);
} while (accept(comma));
expect(semicolon);
}
while (accept(procsym)) {
expect(ident);
expect(semicolon);
block();
expect(semicolon);
}
statement();
}
void program(void) {
getsym();
block();
expect(period);
}
المثال الآخر عبارة عن ترميز شجرة بسيطة وفيها تستدعي وظيفة ترميز الشجرة نفسها لترتيب العقد
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
\ عقد الشجرة تحمل قيم صحيحة وعدادات لعقد أخرى في الشجرة
typedef struct tree_node {
int value;
struct tree_node *left, *right;
} tree_node_t;
\وظيفة لإنشاء الشجرة لإتمام العملية، قم بتجاهلها
tree_node_t *make_tree(void);
\وظيفة لترميز، الشجرة تقوم بترميز الشجرة باستدعاء نفسها
int parse_tree(tree_node_t *root);
int main(void)
{
tree_node_t *a_root = make_tree(); //make a simple tree.
parse_tree(a_root); //parse the tree with parse_tree().
return 0;
}
هذه الوظيفة ليست مهمة//
tree_node_t *make_tree(void)
{
tree_node_t *root = malloc(sizeof(struct tree_node));
tree_node_t *branch1 = malloc(sizeof(struct tree_node));
tree_node_t *branch2 = malloc(sizeof(struct tree_node));
tree_node_t *leaf1 = malloc(sizeof(struct tree_node));
tree_node_t *leaf2 = malloc(sizeof(struct tree_node));
tree_node_t *leaf3 = malloc(sizeof(struct tree_node));
tree_node_t *leaf4 = malloc(sizeof(struct tree_node));
tree_node_t *subleaf = malloc(sizeof(struct tree_node));
root->value = 0;
branch1->value = 1;
branch2->value = 2;
leaf1->value = 3;
leaf2->value =4;
leaf3->value = 5;
leaf4->value = 6;
subleaf->value = 7;
root->left = branch1;
root->right = branch2;
branch1->left = leaf1;
branch1->right = leaf2;
branch2->left = leaf3;
branch2->right = leaf4;
leaf1->left = NULL;
leaf1->right = subleaf;
leaf2->left = NULL;
leaf2->right = NULL;
subleaf->left = NULL;
subleaf->right = NULL;
return root;
}
int parse_tree(tree_node_t *root)
{
printf("Current node value: %in", root->value); //تطبق قيمة العقدة node الحالية.
// راجع للتأكد من أن عدادات العقد عدادات فارغة.
if(root->left && root->right) {
parse_tree(root->left); //تنادي على نفسها، تمر من خلال العقدة (node) اليسرى من خلال.
// الجذر كجذر، محاكية الشجرة.
parse_tree(root->right); //كما بالأعلى.
} else if(root->left) parse_tree(root->left); //إن كان هناك عقدة (node) واحدة فقط فارغة، رمّزها.
else if(root->right) parse_tree(root->right);
else return 0; //إن لم يكن هناك المزيد من العقد (nodes)، توقف.
}
يستخدم الكود السابق التكرار في استعراض شجرة البرنامج من أعلى لأسفل وطباعة القيم المرتبطة بالعقد وهذا مثال نموذجي على التكرار في البرمجة
البناء في لغات البرمجة الوظيفية
الترميز التكراري النموذجي يعتبر سهل البناء بشكل خاص في لغات البرمجة الوظيفية مثل Haskell، Lisp أو ML.
انظر أيضا
- لغات برمجة
مراجع
^ Burge, W.H. (1975). Recursive Programming Techniques. ISBN 0-201-14450-6. .mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
^ Aho، Alfred V.؛ Sethi، Ravi؛ Ullman، Jeffrey (1986). Compilers: Principles, Techniques and Tools (الطبعة first). Addison Wesley. صفحة 183.
تستند هذة المقالة على مواد من قاموس الحوسبة المجاني على الانترنت، وهو ترخيص تحت رخصة جنو للوثائق الحرة.
المترجمات : مبادئ وتقنيات وأدوات, first edition, Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman, in particular Section 4.4.
Modern Compiler Implementation in Java, Second Edition, Andrew Appel, 2002, ISBN 0-521-82060-X.
Recursive Programming Techniques, W.H. Burge, 1975, ISBN 0-201-14450-6
Crafting a Compiler with C, Charles N Fischer and Richard J LeBlanc, Jr, 1991, ISBN 0-8053-2166-7.
Parse::RecDescent: A versatile recursive descent بيرل module.
pyparsing: A versatile Python recursive parsing module that is not recursive descent (python-list post).
Jparsec a Java port of Haskell's Parsec module.
Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X, 624
Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
Compiler Construction, Jonatan Rugarn, 1996, ISBN 0-201-40353-6
وصلات خارجية
Introduction to Parsing - an easy to read introduction to parsing, with a comprehensive section on recursive descent parsing
How to turn a Grammar into C code - a brief tutorial on implementing recursive descent parser
Simple mathematical expressions parser in Ruby
Jack W. Crenshaw: Let's Build A Compiler (1988-1995), in Pascal, with assembler output, using a "keep it simple" approach
بوابة علم الحاسوب
