TTCN-3/C编译器研究与设计
摘要
随着IPv6协议族及相关产品的出现，路由协议测试又成为热点。传统的路由器测试法只能对路由器的单端口或一对端口进行测试，不能全面反映真实网络环境下路由器的功能与性能指标。四川省网络通信重点实验室设计了路由器多端口并发测试系统，该测试系统可以模拟出路由器在实际网络环境下的工作情况，从而可以使测试更准确、更完备。本论文反映的工作是该项研究的测试支撑工具的重要组成部分。
本论文研究的主题是如何将用TTCN-3描述的测试控制数据转变为能够被测试系统执行的可执行测试控制数据的技术。出于多方面考虑，笔者没有采用较为普遍的解释方式，而采用了编译的方式。为了便于与测试系统中其他部件融为一体，首先TTCN-3语言转换成C这种高级语言，相关C代码再与其他部分进行联合编译，最终生成机器代码。
笔者开发的编译器的处理过程分为4个阶段：词法分析、语法分析、语义分析及代码生成。由于不生成最终的机器码，因此，TTCN-3／C编译器生成的代码可以视为中间代码(如许多程序设计编译器的生成汇编语言代码)，因此也不需要考虑最终代码优化问题。本编译器采用两遍扫描。第一遍扫描读入TTCN-3源程序，并对其进行词法分析、语法分析和语义分析。第二遍通过遍历第一遍输出的语法树来完成代码生成。
由于时间关系，本论文中反映的工作仅涵盖词法分析、语法分析、语义分析、构造语法树、符号表的建立以及相关的错误处理。代码生成部分的具体工作由TTCN-3编译器小组的另一位同学完成。为了减少编译器的开发周期，并考虑到其它的一些因素，词法分析部分是用自动构造词法分析的工具LEX的FLEX版本生成的，语法分析部分是用语法分析器的生成器YACC的BISION版本生成的。语义分析部分作为语法分析的子程序，嵌入了YACC的语法规则部分。
其中，语法分析是笔者研究的核心部分。语法分析的难点是如何解决YACC语法规则部分的冲突问题。笔者针对这一问题总结了三种通过改变TTCN-2语法规则部分的书写格式来减少冲突的办法。
西南交通大学硕士研究生学位论文第日页
在语法分析和语义分析阶段设计了语法树和符号表这两个编译器中重要
的数据结构。并且笔者抽象出了fTCN一3中和语义相关的内容。
最后简要介绍了错误处理，以及代码生成的设计思路。
With the advent of IPv6, testing of IPv6 routers has redrawn attentions of the network community. Traditional test methods are only capable of observing and testing a single port or a pair of ports simultaneously. They are not adequate for testing of modern routers in its real working environment, especially in performance testing. This is the very reason for SC-Netcom Lab (Sichuan Network Communication Key Laboratory) to set up the project of CMPT (Concurrent Multi-Port Testing) for IP routers, which can effectively simulate all possible working conditions for multi-port routers. The work presented in this dissertation is part of test support-tool development.
The test control data described in the ISO standardized specification language - TTCN-3 has to be converted into executable code for test systems. The author takes compiling approach instead interpretation as most test systems do in TTCN-3 conversion. The author's comiler involves converting TTCN-3 specifications into C language in order to enable necessary combined compiling with other parts of the test system. In other word, it is a TTCN-3/C compiler.
The compiling process can be divided into four phases: lexical analysis, syntax analysis, semantic analysis, and code generation. The C codes can be thought of as the intermediate codes as in assembly codes in programming language compiling. Therefore, no machine code optimizing process has been involved. The compiling process is composed of two passes in the author compiler. In the first pass, lexical analyzing, syntax analyzing and semantic analyzing are processed, while syntax trees exported from the first pass are used to generating C codes in the compiler.
This dissertation has been dedicated to techniques relevant to lexical analysis, syntax analysis, semantic analysis, syntax tree generation, symbol table construction, and error handling. The work of code generation is done by another student in TTCN-3 compiler working group. FLEX (a new version of popular LEX) is used to automate and speed up lexical analysis and BISON (a version of YACC) is used in syntax analysis by the same token. One of difficulties encountered in syntax analysis is how to solve rule conflicts in YACC. The author
has avoided such conflict by reformatting TTCN-3 rules in YACC and other tactics.
Finally, error handling issues are discussed, and basic idea of code generation is briefly introduced although no programming work has been done in this respect.
本论文研究的主题是如何将用TTCN-3描述的测试控制数据转变为能够被测试系统执行的可执行测试控制数据的技术。出于多方面考虑，笔者没有采用较为普遍的解释方式，而采用了编译的方式。为了便于与测试系统中其他部件融为一体，首先TTCN-3语言转换成C这种高级语言，相关C代码再与其他部分进行联合编译，最终生成机器代码。
笔者开发的编译器的处理过程分为4个阶段：词法分析、语法分析、语义分析及代码生成。由于不生成最终的机器码，因此，TTCN-3／C编译器生成的代码可以视为中间代码(如许多程序设计编译器的生成汇编语言代码)，因此也不需要考虑最终代码优化问题。本编译器采用两遍扫描。第一遍扫描读入TTCN-3源程序，并对其进行词法分析、语法分析和语义分析。第二遍通过遍历第一遍输出的语法树来完成代码生成。
由于时间关系，本论文中反映的工作仅涵盖词法分析、语法分析、语义分析、构造语法树、符号表的建立以及相关的错误处理。代码生成部分的具体工作由TTCN-3编译器小组的另一位同学完成。为了减少编译器的开发周期，并考虑到其它的一些因素，词法分析部分是用自动构造词法分析的工具LEX的FLEX版本生成的，语法分析部分是用语法分析器的生成器YACC的BISION版本生成的。语义分析部分作为语法分析的子程序，嵌入了YACC的语法规则部分。
其中，语法分析是笔者研究的核心部分。语法分析的难点是如何解决YACC语法规则部分的冲突问题。笔者针对这一问题总结了三种通过改变TTCN-2语法规则部分的书写格式来减少冲突的办法。
西南交通大学硕士研究生学位论文第日页
在语法分析和语义分析阶段设计了语法树和符号表这两个编译器中重要
的数据结构。并且笔者抽象出了fTCN一3中和语义相关的内容。
最后简要介绍了错误处理，以及代码生成的设计思路。
With the advent of IPv6, testing of IPv6 routers has redrawn attentions of the network community. Traditional test methods are only capable of observing and testing a single port or a pair of ports simultaneously. They are not adequate for testing of modern routers in its real working environment, especially in performance testing. This is the very reason for SC-Netcom Lab (Sichuan Network Communication Key Laboratory) to set up the project of CMPT (Concurrent Multi-Port Testing) for IP routers, which can effectively simulate all possible working conditions for multi-port routers. The work presented in this dissertation is part of test support-tool development.
The test control data described in the ISO standardized specification language - TTCN-3 has to be converted into executable code for test systems. The author takes compiling approach instead interpretation as most test systems do in TTCN-3 conversion. The author's comiler involves converting TTCN-3 specifications into C language in order to enable necessary combined compiling with other parts of the test system. In other word, it is a TTCN-3/C compiler.
The compiling process can be divided into four phases: lexical analysis, syntax analysis, semantic analysis, and code generation. The C codes can be thought of as the intermediate codes as in assembly codes in programming language compiling. Therefore, no machine code optimizing process has been involved. The compiling process is composed of two passes in the author compiler. In the first pass, lexical analyzing, syntax analyzing and semantic analyzing are processed, while syntax trees exported from the first pass are used to generating C codes in the compiler.
This dissertation has been dedicated to techniques relevant to lexical analysis, syntax analysis, semantic analysis, syntax tree generation, symbol table construction, and error handling. The work of code generation is done by another student in TTCN-3 compiler working group. FLEX (a new version of popular LEX) is used to automate and speed up lexical analysis and BISON (a version of YACC) is used in syntax analysis by the same token. One of difficulties encountered in syntax analysis is how to solve rule conflicts in YACC. The author
has avoided such conflict by reformatting TTCN-3 rules in YACC and other tactics.
Finally, error handling issues are discussed, and basic idea of code generation is briefly introduced although no programming work has been done in this respect.
引文
[1] RFC 2460 - Internet Protocol, Version 6 (IPv6) Specification, December 1998.
[2] 杨洋，余健，李昕昕，论路由器的双端口多功能测试环境的设计．计算机科学，2004．
[3] 李秀峰，张海薇，杨洋．IPv6协议测试技术的探讨．计算机应用，2003，NO．23(增刊)：29～32
[4] RFC 0791-Internet Protocol Specification
[5] Huaxin Zeng and Dave Rayner, "Gateway Testing Technique", in: "Protocol Specification, Testing and Verification", Ⅳ edited By Y. Yemini, and etc., North-holland Publishers, 1984, pp. 637-656
[6] 魏亮．路由器的测试．电信科学，2001．7
[7] ISO/IEC JTC1/SC21, "Information System Technology - Open System Interconnection—Conformance Testing Methodology and Framework" (part 1-7), March 14, 1994
[8] International Standard, Open Systems Interconnection, Conformance testing methodology and framework(ISO/IEC 9646),1994
[9] MingWei Xu, TianPing Wu, "An Extension to Concurrent TTCN", In: Proceedings of IEEE INFOCOM98, San Francisco, U.S.A. March, 1998. 447-454
[10] Huaxin Zeng, Xun Zhou, and Bo Song, "On Testing of IP Routers", in:Proceedings of PACATO3, IEEE press, PP. 535-540, Aug(2003)
[11] 宋波，岳丽全，骆昊，并发多端口路由器测试技术研究．计算机科学，2004．
[12] TTthree - the compiler for the Testing and Test Control Notation TTCN-3. http://www. testingtech. de/
[13] Telco Test Services & TTCN-based Products at Danet. http://www.
danet. de/
[14] ITU-T Recommendation X. 292:OSI Conformance Iesing Methodology and Framework for Protocol Recommendations for ITU-T Applications -the tree and Tabular Combined Notation(TTCN), 1998.
[15] Department of Electrical and Information Engineer, TTCN-3, Telecommunication Software Ⅱ, http://www. danet. de/
[16] ETSI European Standard 201 873-1 TTCN-3:Core Language, 2003.
[17] Anthony Whiles, The tree and tabular combined notation—a tutorial.
[18] Departmentof Electrical and Information Engineer, TTCN-3, Telecommunication Software Ⅱ, http://www.danet. de/
[19] TTCN-3 Online Analyser,http://www. openttcn. com/
[20] 邻居发现协议的形式化测试，http://netlab. cs. tsinghua, edu. cn
[21] L. X. Wang, H. X. Zeng et al., "An Executable Test Case Generation Tool-the CICA TTCN Tool Kit", in: Proceedings of International Conference on Communication Technology", Sep. 1992, Beijing, China.
[22] http://211.96.97.36/cgi-bin/topic, cgi?forum=11&topic=19
[23] 王文娟，钱向红，曾飞，TTCN-3／C编译器设计．计算机科学，2004．
[24] Alfred V．Aho，Ravi Sethi，Jeffrey D．Ullman，编译原理，李建中等译，机械工业出版社，2003．
[25] Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers Principles, Techniques, and Tools,
[26] 吕映芝，编译原理，清华大学出版社，2000．7．
[27] Introduction Flex, http://www. fsf. org/software/flex
[28] Bennett, J.P. Introduction to Compiling Techniques - A First Course Using Ansi C, Lex and Yacc. McGraw Hill Book Co, 1990.
[29] M. E. Lesk Lex- A Lexical Analyzer Generator, Comp, Sci, Tech, Rep, No. 39, Bell Laboratories, October 1975.
[30] Schreiner, Axel T. and H. Gerorge Friedman, Jr. Introduction to Compiler Construction with UNIX. Prentice-Hall, 1985.
[31] http://www. linuxjournal. com/article. php?sid=2227
[32] http://www. monmouth. com/～wstreett/lex-yacc/flex_1. html
[33] Deloria, "Practical yacc: a gentle introduction to the power of this famous parser generator."C Users Journal, Nov 1987, Dec/Jan 1988, Mar/Apr 1988, Jun/Jul 1988, and Sep/Oct 1988.
[34] S. C. Johnson Yacc-Yet Another Compiler, Comp. Sci. Tech. Rep. No. 32, Bell Laboratories, July 1975.
[35] Lesk M. E. Schmidt E. Lex-Lexical Analyser Generator in UNIX Programmer's Manual Vol. 2
[36] yacc information, http://www. programming-x. com/programming/ yacc. html
[37] Yacc-A parser generator, http://www. luv. asn. au/overheads /lex_yacc/yacc. html
[38] yacc与lex快速入门，http://www-900.ibm.com/developerWorks/cn/linux/sdk/lex/index.shtml
[39] 词法分析工具和语法分析工具，http://ultral.wuhee.edu.cn/compiler/compiler.html
[40] Introduction to Parsing and Inside YACC, http://www. mactech. com/articles/mactech/Vol. 06/06.04/ParsingwithYACC/
[41] Donnely and Stallman, The Bison Manual, Part of the online bison distribution.
[42] http://www. gnu. org/manual/bison/index. html
[43] Jobn R．Levine，Tony Mason，Doug Brown，lex与yacc，杨作梅等译，机械工业出版社，2003．
[44] Jobn R.Levine, Tony Mason, Doug Brown, lex & yacc, O' Reilly & Associates, Inc, 1992.
[45] Kenneth C．Louden，编译原理与实践，机械工业出版社，2001．1．
[46] Dick Grune，Henri E．Bal，现代编译程序设计，人民邮电出版社
[47] 严蔚敏，吴伟民，数据结构，清华大学出版社，1997．4．
[48]Steven S．MuchniCk，高级编译器设计与实现(英文版)，机械工业出版社．
[49]陈火旺，刘春林，程序设计语言编译原理，国防工业出版社，2000．1．
[50]杜淑敏，王永宁，编译程序设计原理，科学出版社，1990．
[2] 杨洋，余健，李昕昕，论路由器的双端口多功能测试环境的设计．计算机科学，2004．
[3] 李秀峰，张海薇，杨洋．IPv6协议测试技术的探讨．计算机应用，2003，NO．23(增刊)：29～32
[4] RFC 0791-Internet Protocol Specification
[5] Huaxin Zeng and Dave Rayner, "Gateway Testing Technique", in: "Protocol Specification, Testing and Verification", Ⅳ edited By Y. Yemini, and etc., North-holland Publishers, 1984, pp. 637-656
[6] 魏亮．路由器的测试．电信科学，2001．7
[7] ISO/IEC JTC1/SC21, "Information System Technology - Open System Interconnection—Conformance Testing Methodology and Framework" (part 1-7), March 14, 1994
[8] International Standard, Open Systems Interconnection, Conformance testing methodology and framework(ISO/IEC 9646),1994
[9] MingWei Xu, TianPing Wu, "An Extension to Concurrent TTCN", In: Proceedings of IEEE INFOCOM98, San Francisco, U.S.A. March, 1998. 447-454
[10] Huaxin Zeng, Xun Zhou, and Bo Song, "On Testing of IP Routers", in:Proceedings of PACATO3, IEEE press, PP. 535-540, Aug(2003)
[11] 宋波，岳丽全，骆昊，并发多端口路由器测试技术研究．计算机科学，2004．
[12] TTthree - the compiler for the Testing and Test Control Notation TTCN-3. http://www. testingtech. de/
[13] Telco Test Services & TTCN-based Products at Danet. http://www.
danet. de/
[14] ITU-T Recommendation X. 292:OSI Conformance Iesing Methodology and Framework for Protocol Recommendations for ITU-T Applications -the tree and Tabular Combined Notation(TTCN), 1998.
[15] Department of Electrical and Information Engineer, TTCN-3, Telecommunication Software Ⅱ, http://www. danet. de/
[16] ETSI European Standard 201 873-1 TTCN-3:Core Language, 2003.
[17] Anthony Whiles, The tree and tabular combined notation—a tutorial.
[18] Departmentof Electrical and Information Engineer, TTCN-3, Telecommunication Software Ⅱ, http://www.danet. de/
[19] TTCN-3 Online Analyser,http://www. openttcn. com/
[20] 邻居发现协议的形式化测试，http://netlab. cs. tsinghua, edu. cn
[21] L. X. Wang, H. X. Zeng et al., "An Executable Test Case Generation Tool-the CICA TTCN Tool Kit", in: Proceedings of International Conference on Communication Technology", Sep. 1992, Beijing, China.
[22] http://211.96.97.36/cgi-bin/topic, cgi?forum=11&topic=19
[23] 王文娟，钱向红，曾飞，TTCN-3／C编译器设计．计算机科学，2004．
[24] Alfred V．Aho，Ravi Sethi，Jeffrey D．Ullman，编译原理，李建中等译，机械工业出版社，2003．
[25] Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers Principles, Techniques, and Tools,
[26] 吕映芝，编译原理，清华大学出版社，2000．7．
[27] Introduction Flex, http://www. fsf. org/software/flex
[28] Bennett, J.P. Introduction to Compiling Techniques - A First Course Using Ansi C, Lex and Yacc. McGraw Hill Book Co, 1990.
[29] M. E. Lesk Lex- A Lexical Analyzer Generator, Comp, Sci, Tech, Rep, No. 39, Bell Laboratories, October 1975.
[30] Schreiner, Axel T. and H. Gerorge Friedman, Jr. Introduction to Compiler Construction with UNIX. Prentice-Hall, 1985.
[31] http://www. linuxjournal. com/article. php?sid=2227
[32] http://www. monmouth. com/～wstreett/lex-yacc/flex_1. html
[33] Deloria, "Practical yacc: a gentle introduction to the power of this famous parser generator."C Users Journal, Nov 1987, Dec/Jan 1988, Mar/Apr 1988, Jun/Jul 1988, and Sep/Oct 1988.
[34] S. C. Johnson Yacc-Yet Another Compiler, Comp. Sci. Tech. Rep. No. 32, Bell Laboratories, July 1975.
[35] Lesk M. E. Schmidt E. Lex-Lexical Analyser Generator in UNIX Programmer's Manual Vol. 2
[36] yacc information, http://www. programming-x. com/programming/ yacc. html
[37] Yacc-A parser generator, http://www. luv. asn. au/overheads /lex_yacc/yacc. html
[38] yacc与lex快速入门，http://www-900.ibm.com/developerWorks/cn/linux/sdk/lex/index.shtml
[39] 词法分析工具和语法分析工具，http://ultral.wuhee.edu.cn/compiler/compiler.html
[40] Introduction to Parsing and Inside YACC, http://www. mactech. com/articles/mactech/Vol. 06/06.04/ParsingwithYACC/
[41] Donnely and Stallman, The Bison Manual, Part of the online bison distribution.
[42] http://www. gnu. org/manual/bison/index. html
[43] Jobn R．Levine，Tony Mason，Doug Brown，lex与yacc，杨作梅等译，机械工业出版社，2003．
[44] Jobn R.Levine, Tony Mason, Doug Brown, lex & yacc, O' Reilly & Associates, Inc, 1992.
[45] Kenneth C．Louden，编译原理与实践，机械工业出版社，2001．1．
[46] Dick Grune，Henri E．Bal，现代编译程序设计，人民邮电出版社
[47] 严蔚敏，吴伟民，数据结构，清华大学出版社，1997．4．
[48]Steven S．MuchniCk，高级编译器设计与实现(英文版)，机械工业出版社．
[49]陈火旺，刘春林，程序设计语言编译原理，国防工业出版社，2000．1．
[50]杜淑敏，王永宁，编译程序设计原理，科学出版社，1990．