免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › CPU与编译器 › gcc中C语言的词法分析是怎么做的?
12下一页
最近访问板块 发新帖
查看: 8353 | 回复: 13
打印 上一主题 下一主题

gcc中C语言的词法分析是怎么做的? [复制链接]

qtdszws

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2009-05-16 10:16 |只看该作者 |倒序浏览
版本4.3.0，原以为会使用flex,搜索到一些l文件，看内容不像。上网搜，说会调用c-opts.c中c_common_parse_file，循着这个线索找了下去，最好找到libcpp/lex.c中的_cpp_lex_direct，发现尽然是手动分析。


  2. cpp_token *
  3. _cpp_lex_direct (cpp_reader *pfile)
  4. {
  5.   cppchar_t c;
  6.   cpp_buffer *buffer;
  7.   const unsigned char *comment_start;
  8.   cpp_token *result = pfile->cur_token++;

  10. fresh_line:
  11.   result->flags = 0;
  12.   buffer = pfile->buffer;
  13.   if (buffer->need_line)
  14.     {
  15.       if (pfile->state.in_deferred_pragma)
  16.         {
  17.           result->type = CPP_PRAGMA_EOL;
  18.           pfile->state.in_deferred_pragma = false;
  19.           if (!pfile->state.pragma_allow_expansion)
  20.             pfile->state.prevent_expansion--;
  21.           return result;
  22.         }
  23.       if (!_cpp_get_fresh_line (pfile))
  24.         {
  25.           result->type = CPP_EOF;
  26.           if (!pfile->state.in_directive)
  27.             {
  28.               /* Tell the compiler the line number of the EOF token.  */
  29.               result->src_loc = pfile->line_table->highest_line;
  30.               result->flags = BOL;
  31.             }
  32.           return result;
  33.         }
  34.       if (!pfile->keep_tokens)
  35.         {
  36.           pfile->cur_run = &pfile->base_run;
  37.           result = pfile->base_run.base;
  38.           pfile->cur_token = result + 1;
  39.         }
  40.       result->flags = BOL;
  41.       if (pfile->state.parsing_args == 2)
  42.         result->flags |= PREV_WHITE;
  43.     }
  44.   buffer = pfile->buffer;
  45. update_tokens_line:
  46.   result->src_loc = pfile->line_table->highest_line;

  48. skipped_white:
  49.   if (buffer->cur >= buffer->notes[buffer->cur_note].pos
  50.       && !pfile->overlaid_buffer)
  51.     {
  52.       _cpp_process_line_notes (pfile, false);
  53.       result->src_loc = pfile->line_table->highest_line;
  54.     }
  55.   c = *buffer->cur++;

  57.   LINEMAP_POSITION_FOR_COLUMN (result->src_loc, pfile->line_table,
  58.                                CPP_BUF_COLUMN (buffer, buffer->cur));

  60.   switch (c)
  61.     {
  62.     case ' ': case '\t': case '\f': case '\v': case '\0':
  63.       result->flags |= PREV_WHITE;
  64.       skip_whitespace (pfile, c);
  65.       goto skipped_white;

  67.     case '\n':
  68.       if (buffer->cur < buffer->rlimit)
  69.         CPP_INCREMENT_LINE (pfile, 0);
  70.       buffer->need_line = true;
  71.       goto fresh_line;

  73.     case '0': case '1': case '2': case '3': case '4':
  74.     case '5': case '6': case '7': case '8': case '9':
  75.       {
  76.         struct normalize_state nst = INITIAL_NORMALIZE_STATE;
  77.         result->type = CPP_NUMBER;
  78.         lex_number (pfile, &result->val.str, &nst);
  79.         warn_about_normalization (pfile, result, &nst);
  80.         break;
  81.       }

  83.     case 'L':
  84.       /* 'L' may introduce wide characters or strings.  */
  85.       if (*buffer->cur == '\'' || *buffer->cur == '"')
  86.         {
  87.           lex_string (pfile, result, buffer->cur - 1);
  88.           break;
  89.         }
  90.       /* Fall through.  */

  92.     case '_':
  93.     case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
  94.     case 'g': case 'h': case 'i': case 'j': case 'k': case 'l':
  95.     case 'm': case 'n': case 'o': case 'p': case 'q': case 'r':
  96.     case 's': case 't': case 'u': case 'v': case 'w': case 'x':
  97.     case 'y': case 'z':
  98.     case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
  99.     case 'G': case 'H': case 'I': case 'J': case 'K':
  100.     case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R':
  101.     case 'S': case 'T': case 'U': case 'V': case 'W': case 'X':
  102.     case 'Y': case 'Z':
  103.       result->type = CPP_NAME;
  104.       {
  105.         struct normalize_state nst = INITIAL_NORMALIZE_STATE;
  106.         result->val.node = lex_identifier (pfile, buffer->cur - 1, false,
  107.                                            &nst);
  108.         warn_about_normalization (pfile, result, &nst);
  109.       }

  111.       /* Convert named operators to their proper types.  */
  112.       if (result->val.node->flags & NODE_OPERATOR)
  113.         {
  114.           result->flags |= NAMED_OP;
  115.           result->type = (enum cpp_ttype) result->val.node->directive_index;
  116.         }
  117.       break;

  119.     case '\'':
  120.     case '"':
  121.       lex_string (pfile, result, buffer->cur - 1);
  122.       break;

  124.     case '/':
  125.       /* A potential block or line comment.  */
  126.       comment_start = buffer->cur;
  127.       c = *buffer->cur;
  128.       
  129.       if (c == '*')
  130.         {
  131.           if (_cpp_skip_block_comment (pfile))
  132.             cpp_error (pfile, CPP_DL_ERROR, "unterminated comment");
  133.         }
  134.       else if (c == '/' && (CPP_OPTION (pfile, cplusplus_comments)
  135.                             || cpp_in_system_header (pfile)))
  136.         {
  137.           /* Warn about comments only if pedantically GNUC89, and not
  138.              in system headers.  */
  139.           if (CPP_OPTION (pfile, lang) == CLK_GNUC89 && CPP_PEDANTIC (pfile)
  140.               && ! buffer->warned_cplusplus_comments)
  141.             {
  142.               cpp_error (pfile, CPP_DL_PEDWARN,
  143.                          "C++ style comments are not allowed in ISO C90");
  144.               cpp_error (pfile, CPP_DL_PEDWARN,
  145.                          "(this will be reported only once per input file)");
  146.               buffer->warned_cplusplus_comments = 1;
  147.             }

  149.           if (skip_line_comment (pfile) && CPP_OPTION (pfile, warn_comments))
  150.             cpp_error (pfile, CPP_DL_WARNING, "multi-line comment");
  151.         }
  152.       else if (c == '=')
  153.         {
  154.           buffer->cur++;
  155.           result->type = CPP_DIV_EQ;
  156.           break;
  157.         }
  158.       else
  159.         {
  160.           result->type = CPP_DIV;
  161.           break;
  162.         }

  164.       if (!pfile->state.save_comments)
  165.         {
  166.           result->flags |= PREV_WHITE;
  167.           goto update_tokens_line;
  168.         }

  170.       /* Save the comment as a token in its own right.  */
  171.       save_comment (pfile, result, comment_start, c);
  172.       break;

  174.     case '<':
  175.       if (pfile->state.angled_headers)
  176.         {
  177.           lex_string (pfile, result, buffer->cur - 1);
  178.           break;
  179.         }

  181.       result->type = CPP_LESS;
  182.       if (*buffer->cur == '=')
  183.         buffer->cur++, result->type = CPP_LESS_EQ;
  184.       else if (*buffer->cur == '<')
  185.         {
  186.           buffer->cur++;
  187.           IF_NEXT_IS ('=', CPP_LSHIFT_EQ, CPP_LSHIFT);
  188.         }
  189.       else if (CPP_OPTION (pfile, digraphs))
  190.         {
  191.           if (*buffer->cur == ':')
  192.             {
  193.               buffer->cur++;
  194.               result->flags |= DIGRAPH;
  195.               result->type = CPP_OPEN_SQUARE;
  196.             }
  197.           else if (*buffer->cur == '%')
  198.             {
  199.               buffer->cur++;
  200.               result->flags |= DIGRAPH;
  201.               result->type = CPP_OPEN_BRACE;
  202.             }
  203.         }
  204.       break;

  206.     case '>':
  207.       result->type = CPP_GREATER;
  208.       if (*buffer->cur == '=')
  209.         buffer->cur++, result->type = CPP_GREATER_EQ;
  210.       else if (*buffer->cur == '>')
  211.         {
  212.           buffer->cur++;
  213.           IF_NEXT_IS ('=', CPP_RSHIFT_EQ, CPP_RSHIFT);
  214.         }
  215.       break;

  217.     case '%':
  218.       result->type = CPP_MOD;
  219.       if (*buffer->cur == '=')
  220.         buffer->cur++, result->type = CPP_MOD_EQ;
  221.       else if (CPP_OPTION (pfile, digraphs))
  222.         {
  223.           if (*buffer->cur == ':')
  224.             {
  225.               buffer->cur++;
  226.               result->flags |= DIGRAPH;
  227.               result->type = CPP_HASH;
  228.               if (*buffer->cur == '%' && buffer->cur[1] == ':')
  229.                 buffer->cur += 2, result->type = CPP_PASTE;
  230.             }
  231.           else if (*buffer->cur == '>')
  232.             {
  233.               buffer->cur++;
  234.               result->flags |= DIGRAPH;
  235.               result->type = CPP_CLOSE_BRACE;
  236.             }
  237.         }
  238.       break;

  240.     case '.':
  241.       result->type = CPP_DOT;
  242.       if (ISDIGIT (*buffer->cur))
  243.         {
  244.           struct normalize_state nst = INITIAL_NORMALIZE_STATE;
  245.           result->type = CPP_NUMBER;
  246.           lex_number (pfile, &result->val.str, &nst);
  247.           warn_about_normalization (pfile, result, &nst);
  248.         }
  249.       else if (*buffer->cur == '.' && buffer->cur[1] == '.')
  250.         buffer->cur += 2, result->type = CPP_ELLIPSIS;
  251.       else if (*buffer->cur == '*' && CPP_OPTION (pfile, cplusplus))
  252.         buffer->cur++, result->type = CPP_DOT_STAR;
  253.       break;

  255.     case '+':
  256.       result->type = CPP_PLUS;
  257.       if (*buffer->cur == '+')
  258.         buffer->cur++, result->type = CPP_PLUS_PLUS;
  259.       else if (*buffer->cur == '=')
  260.         buffer->cur++, result->type = CPP_PLUS_EQ;
  261.       break;

  263.     case '-':
  264.       result->type = CPP_MINUS;
  265.       if (*buffer->cur == '>')
  266.         {
  267.           buffer->cur++;
  268.           result->type = CPP_DEREF;
  269.           if (*buffer->cur == '*' && CPP_OPTION (pfile, cplusplus))
  270.             buffer->cur++, result->type = CPP_DEREF_STAR;
  271.         }
  272.       else if (*buffer->cur == '-')
  273.         buffer->cur++, result->type = CPP_MINUS_MINUS;
  274.       else if (*buffer->cur == '=')
  275.         buffer->cur++, result->type = CPP_MINUS_EQ;
  276.       break;

  278.     case '&':
  279.       result->type = CPP_AND;
  280.       if (*buffer->cur == '&')
  281.         buffer->cur++, result->type = CPP_AND_AND;
  282.       else if (*buffer->cur == '=')
  283.         buffer->cur++, result->type = CPP_AND_EQ;
  284.       break;

  286.     case '|':
  287.       result->type = CPP_OR;
  288.       if (*buffer->cur == '|')
  289.         buffer->cur++, result->type = CPP_OR_OR;
  290.       else if (*buffer->cur == '=')
  291.         buffer->cur++, result->type = CPP_OR_EQ;
  292.       break;

  294.     case ':':
  295.       result->type = CPP_COLON;
  296.       if (*buffer->cur == ':' && CPP_OPTION (pfile, cplusplus))
  297.         buffer->cur++, result->type = CPP_SCOPE;
  298.       else if (*buffer->cur == '>' && CPP_OPTION (pfile, digraphs))
  299.         {
  300.           buffer->cur++;
  301.           result->flags |= DIGRAPH;
  302.           result->type = CPP_CLOSE_SQUARE;
  303.         }
  304.       break;

  306.     case '*': IF_NEXT_IS ('=', CPP_MULT_EQ, CPP_MULT); break;
  307.     case '=': IF_NEXT_IS ('=', CPP_EQ_EQ, CPP_EQ); break;
  308.     case '!': IF_NEXT_IS ('=', CPP_NOT_EQ, CPP_NOT); break;
  309.     case '^': IF_NEXT_IS ('=', CPP_XOR_EQ, CPP_XOR); break;
  310.     case '#': IF_NEXT_IS ('#', CPP_PASTE, CPP_HASH); break;

  312.     case '?': result->type = CPP_QUERY; break;
  313.     case '~': result->type = CPP_COMPL; break;
  314.     case ',': result->type = CPP_COMMA; break;
  315.     case '(': result->type = CPP_OPEN_PAREN; break;
  316.     case ')': result->type = CPP_CLOSE_PAREN; break;
  317.     case '[': result->type = CPP_OPEN_SQUARE; break;
  318.     case ']': result->type = CPP_CLOSE_SQUARE; break;
  319.     case '{': result->type = CPP_OPEN_BRACE; break;
  320.     case '}': result->type = CPP_CLOSE_BRACE; break;
  321.     case ';': result->type = CPP_SEMICOLON; break;

  323.       /* @ is a punctuator in Objective-C.  */
  324.     case '@': result->type = CPP_ATSIGN; break;

  326.     case '$':
  327.     case '\\':
  328.       {
  329.         const uchar *base = --buffer->cur;
  330.         struct normalize_state nst = INITIAL_NORMALIZE_STATE;

  332.         if (forms_identifier_p (pfile, true, &nst))
  333.           {
  334.             result->type = CPP_NAME;
  335.             result->val.node = lex_identifier (pfile, base, true, &nst);
  336.             warn_about_normalization (pfile, result, &nst);
  337.             break;
  338.           }
  339.         buffer->cur++;
  340.       }

  342.     default:
  343.       create_literal (pfile, result, buffer->cur - 1, 1, CPP_OTHER);
  344.       break;
  345.     }

  347.   return result;
  348. }
复制代码
jzhang918

论坛徽章:
0
2楼 [报告]
发表于 2009-05-16 18:19 |只看该作者

回复 #1 qtdszws 的帖子

gcc 里的c和c＋＋最早的时候都是用lex/yacc。后来先是c++改成了手工写的recursive descent语法分析器，然后c也改成手工写的了。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
emmoblin

论坛徽章:
0
3楼 [报告]
发表于 2009-05-17 00:31 |只看该作者
语法，词法分析比较简单，技术都成熟了，怎么写都行。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
qtdszws

论坛徽章:
0
4楼 [报告]
发表于 2009-05-17 22:45 |只看该作者
查了一下，v4.3.0的语法分析果然是用手工编写的（gcc/c-parser.c中 c_parse_file，8千行代码,还有一个gcc/cp/parser.c,2万行代码），巨汗！继续往前查，发现所能找到的最早版本v1.21(ftp://gcc.gnu.org/pub/gcc/old-releases/gcc-1/)的词法分析仍然是手工编写的，而语法分析是bison生成的。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
system888net

论坛徽章:
0
5楼 [报告]
发表于 2009-05-19 21:15 |只看该作者
原帖由 emmoblin 于 2009-5-17 00:31 发表
语法，词法分析比较简单，技术都成熟了，怎么写都行。


说的是.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
qtdszws

论坛徽章:
0
6楼 [报告]
发表于 2009-05-20 09:00 |只看该作者
那么请问，如何手工编写语法分析程序呢？

例如
S->aAcBe
A->b
A->Ab
B->d
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
Solidus

论坛徽章:
0
7楼 [报告]
发表于 2009-05-21 05:05 |只看该作者
原帖由 qtdszws 于 2009-5-20 09:00 发表
那么请问，如何手工编写语法分析程序呢？

例如
S->aAcBe
A->b
A->Ab
B->d



简单点纯手工编码的多数是针对LL的递归下降，大概做法就是先手工或者自动化的消除文法左递归和左因子，求first follow集合，针对LR的也存在一种叫低递归上升的编码方式，不过我不会也没见过这个，你可以搜一下。
递归下降比较好懂的例子就是计算器(里面有我刚学这类东西的时候扯的淡，这些淡你最好过滤掉它们，我当时也是一脑子浆糊)。

PS：这类东西都是成套路的，入门的话最好还是先学点简单的图算法，最起码龙书上那点自动机相关的（LL,SLR,LR,LALR）parser算法往图搜索上一套基本上就出来了，区别不过是构造顶点和边的方式不同(我个人认为纯手工的递归下降或者表驱动都属于对生成的图的用法不同，彻底弄明白一个也就都明白了)。

[ 本帖最后由 Solidus 于 2009-5-21 05:08 编辑 ]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cathyleung

论坛徽章:
0
8楼 [报告]
发表于 2009-05-25 09:57 |只看该作者
撑啊～好贴子～
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
gta

论坛徽章:
0
9楼 [报告]
发表于 2009-05-25 22:15 |只看该作者
原帖由 qtdszws 于 2009-5-20 09:00 发表
那么请问，如何手工编写语法分析程序呢？

例如
S->aAcBe
A->b
A->Ab
B->d



首先要对语法做变换，消除A->Ab中的左递归，变换后的语法是
S->aAcBe
A->bA | epsilon
B->d


这是一个LL(1) grammar, 龙书第二版第四章算法4.31就是LL(1) parsing table的构造算法，算法4.34是表驱动的predictive parsing算法

[ 本帖最后由 gta 于 2009-5-25 22:19 编辑 ]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
norechang

论坛徽章:
0
10楼 [报告]
发表于 2009-05-27 11:44 |只看该作者

回复 #9 gta 的帖子

將 A- >b| Ab 改成
A->bA | epsilon
是有問題的
如此會產生'acde'這個string, 而此string
不屬於原本的grammar
left recursive 的改寫公式如下
A -> Aa|b
改寫成
A -> bR
R -> aR | epsilon

故於原始grammar裡，
A->b|Ab
可修改成
A->bR
R->bR | epsilon

LL(1) parser的建構方式很簡單，以
S->aAcBe為例：

S()
{
   if(lookahead() == 'a')
      match('a);
   else
      throw error;
   
   A();

   if(lookahead() == 'c')
     match('c');
   else
     throw error;

   B();

   if(lookahead() == 'e')
     match('e');
   else
     throw error;
}

其中 lookahead 會取出下一個token, match 會比較並消耗一個token
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP