0%

中断和异常处理

中断和异常处理概述

中断和异常是表明在系统、处理器的某个地方存在一个条件的事件,或当前执行的程序或任务中存在需要处理器注意的情况。它们通常会强制将进程从当前运行的程序或任务转移到一个特殊的软件程序或任务上,称为中断处理程序或异常处理程序。处理器为响应中断或异常而采取的行动被称为中断或异常处理。
中断在程序执行过程中随机发生,以响应来自硬件的信号。系统硬件使用中断来处理处理器外部的事件,如服务外围设备的请求。软件也可以通过执行INT n指令来产生中断。当处理器在执行指令时检测到一个错误条件,如除以0,就会发生异常。处理器检测各种错误条件,包括违反保护规定、页面故障和内部机器故障。
奔腾4、英特尔至强、P6系列和奔腾处理器的机器,当检测到内部硬件错误和总线错误时,也允许产生一个机器检查异常。
当处理器执行一个中断或异常处理程序时,当前运行的程序或任务被暂停。当处理程序的执行完成后,处理器恢复被中断的程序或任务的执行。除非无法从异常中恢复,或者中断导致当前运行的程序被终止,否则被中断的程序或任务的恢复不会失去程序的连续性。
在实模式下,中断向量表占据内存最低的1KB,共256个表项。每个表项4子节,包含一个2子节的段地址和2子节的偏移,即中断处理程序的入口地址。但是在保护模式下,中断向量表可以在内存中自由浮动。就像GDT被GDTR指向一样,中断向量表被IDTR(Interrupt Descriptor Table Register,中断描述符表寄存器)指向。该表和GDT非常类似。首先,GDTR和IDTR在格式上完全相同,均包含一个32bit的基地址和16bit的界限。相比之下,CPU中的另外两个关键寄存器LDTR和TR则表现出了相似性,都是16bit大小,分别包含指向LDT和TSS的选择子。从表项上来看,除了指出中断处理程序的目标地址(16bit选择子和32bit偏移)外,IDT表项还为了进行特权级检测而加入的DPL域。此外,IDT表项还包含一个P比特。

有关中断和异常了解性的内容

中断和异常向量

为了帮助处理异常和中断,每个架构上定义的异常和每个中断条件都被分配了一个唯一的识别号,称为向量号。处理器使用分配给一个异常或中断的向量号作为中断描述符表(IDT)的索引。该表提供了一个异常或中断处理程序的入口点。矢量号的允许范围是0到255。在0到31的范围内的向量号是由英特尔64和IA-32架构为架构定义的异常和中断保留了向量号。并非所有的向量号在这个范围内,并不是所有的向量号都有一个当前定义的功能。
在32到255范围内的向量号被指定为用户定义的中断,不被Intel64和IA-32架构保留。这些中断通常被分配给外部I/O设备,使这些设备能够向处理器发送中断。

中断源和异常源

中断来源

处理器接收来自两个来源的中断。

  • 外部(硬件产生的)中断。
  • 软件产生的中断
外部中断

外部中断是通过处理器上的引脚或通过本地APIC接收的。Pentium 4、Intel Xeon、P6系列和Pentium处理器的主要中断引脚是LINT[1:0]引脚,它与本地APIC相连。启用时,LINT[1:0]引脚可以通过APIC的本地向量表(LVT)进行编程,以便与处理器的任何异常或故障相关联。

image-20220410193839865

image-20220410193850982

可屏蔽的硬件中断

任何通过INTR引脚或通过本地APIC传递给处理器的外部中断被称为可屏蔽硬件中断。可以通过INTR引脚传送的可屏蔽硬件中断包括所有IA-32体系结构定义的从0到255的中断向量;那些可通过本地APIC传送的中断包括中断向量16到255。

软件产生的中断

INT n指令允许通过提供一个中断向量作为操作数,从软件内部产生中断。例如,INT 35指令强制调用35号中断的中断处理程序。任何从0到255的中断向量都可以作为该指令的参数。如果使用了处理器预定义的NMI向量,那么处理器的反应将与正常产生的的NMI中断产生的反应不一样。如果在这条指令中使用了2号向量(NMI向量),就会调用NMI中断处理程序,但处理器的NMI处理硬件没有被激活。用INT n指令在软件中产生的中断不能被EFLAGS寄存器中的IF标志所屏蔽。

异常来源

处理器接收来自三个来源的异常。

  • 处理器检测到的程序错误异常。
  • 软件产生的异常。
  • 机器检查的异常。
程序错误异常

当处理器在应用程序或操作系统或执行程序的执行过程中检测到程序错误时,会产生一个或多个异常。英特尔64和IA-32架构为每个处理器检测到的异常定义了一个向量号。

软件产生的异常

INTO, INT 3, 和 BOUND 指令允许在软件中产生异常。这些指令允许异常条件的检查在指令流中执行。例如,INT 3产生一个断点异常。INT n指令可以用来模拟软件中的异常;但是有一个限制。如果INT n提供了一个架构定义的异常的向量,处理器会产生一个中断到正确的向量(来访问异常处理程序),但不会在堆栈上推送错误代码。

机器检查异常

P6系列和奔腾处理器提供内部和外部机器检查机制,用于检查内部芯片硬件和总线交易的操作。这些机制取决于执行情况。当检测到机器检查错误时,处理器发出机器检查异常信号(向量18)并返回一个错误代码。

异常的分类:故障、陷阱和中止

异常被归类为故障、陷阱或中止,这取决于它们的报告方式以及引起异常的指令是否能在不损失程序或任务连续性的情况下重新启动。

  • 故障

故障是一种通常可以被纠正的异常,一旦被纠正,就可以在不损失程序或任务连续性的情况下重新启动程序。
当一个故障被报告时,处理器将机器状态恢复到在开始执行故障指令之前的状态。故障处理程序的返回地址(保存在CS和EIP寄存器的保存内容)指向故障指令,而不是指向故障指令之后的指令。

  • 陷阱

    陷阱是在执行陷阱指令后立即报告的异常。陷阱允许程序或任务的执行继续进行而不损失程序的连续性。陷阱处理程序的返回地址指向陷阱指令后要执行的指令。

  • 终止

    终止是一种异常,它并不总是报告引起异常的指令的精确位置,并且不允许重新启动引起异常的程序或任务。中止是用来报告严重的错误,例如硬件错误和系统表中不一致的或非法的值。

注意

一个通常被报告为故障的异常子集是不能重新启动的。这种异常会导致损失一些处理器的状态。例如,在执行POPAD指令时,堆栈框架执行POPAD指令时,堆栈框架越过了堆栈段的末端,导致报告了一个故障。在这种情况下,异常处理程序看到指令指针(CS:EIP)已经被恢复,就像POPAD 指令没有被执行。然而,内部处理器状态(通用寄存器)将被修改。这种情况被认为是编程错误

程序或任务的重新执行

为了允许在处理异常或中断后重新启动程序或任务,所有的异常(除了中止)都保证在指令边界上报告异常。所有的中断都被保证为在一个指令边界上进行。
对于故障类异常,返回指令指针(在处理器产生异常时保存)指向发生故障的指令。因此,当一个程序或任务在处理完故障后被重新启动时,发生故障的指令被重新启动(重新执行)。重启出错指令通常用于处理当对操作数的访问被阻止时产生的异常。这种类型的故障最常见的例子是页面故障异常(#PF),它发生在程序或任务引用位于不在内存中的页面上的操作数时。
当页面故障异常发生时,异常处理程序可以将该页面加载到内存中,并通过重启来恢复程序或任务的执行。为了确保重启对当前执行的程序或任务来说是透明的,处理器保存了必要的寄存器和堆栈指针 ,以允许重新启动到执行故障指令之前的状态。
对于陷阱类异常,返回指令的指针指向陷阱指令之后的指令。如果在转移执行的指令中检测到一个陷阱,返回指令指针反映了转移。例如,如果在执行JMP指令时检测到一个陷阱,返回指令的指针指向JMP指令的目的地,而不是JMP指令之后的下一个地址。所有的陷阱异常都允许程序或任务的重新启动而不会失去连续性。例如,溢出异常就是一个陷阱异常。在这里,返回指令的指针指向INTO指令之后的指令,该指令测试了EFLAGS.OF(溢出)标志。这个异常的陷阱处理程序解决了溢出的问题。从陷阱处理程序返回后,程序或任务在INTO指令之后的指令继续执行。
终止类异常不支持程序或任务的可靠重启。终止处理程序被设计为收集关于终止异常发生时处理器状态的诊断信息,然后尽可能优雅地关闭应用程序和系统。
中断程序严格地支持重新启动被中断的程序和任务而不损失连续性。返回为中断保存的返回指令指针指向要在指令边界执行的下一条指令 。如果刚刚执行的指令有一个重复的前缀,那么中断就会在当前迭代结束时进行,寄存器被设置为执行下一个迭代。

开启和禁止中断

处理器会抑制一些中断的产生,这取决于处理器的状态和EFLAGS寄存器中的IF和RF标志的状态。

屏蔽可屏蔽硬件中断

IF标志可以禁止对处理器INTR引脚上或通过本地APIC接收的可屏蔽硬件中断进行服务。当IF标志清除时,处理器会抑制传递到INTR引脚或通过本地APIC的中断产生内部中断请求;当IF标志被设置时,传递到INTR或通过本地APIC引脚的中断被作为正常的外部中断处理。
IF标志不影响传递到NMI引脚的非屏蔽中断(NMI)或通过本地APIC传递的交付模式NMI消息,也不影响处理器产生的异常。与EFLAGS寄存器中的其他标志一样,处理器在响应硬件复位时清除IF标志。
事实上,可屏蔽的硬件中断组包括保留的中断和异常向量0到32可能会引起混淆。从结构上看,当IF标志被设置时,矢量0到32的中断可以通过INTR引脚传递给处理器,而矢量16到32的中断则可以通过本地接口传递。然后,处理器将产生一个中断并调用中断或异常处理程序,该处理程序由矢量编号指向。
IF标志可以通过STI(设置中断使能标志)和CLI(清除中断使能标志)指令来设置或清除。这些指令只有在CPL等于或小于IOPL的情况下才能执行。如果在CPL大于IOPL的情况下执行这些指令,会产生一般保护异常(#GP)。
IF标志也受到以下操作的影响。

  • PUSHF指令将所有的标志存储在堆栈上,在那里可以检查和修改它们。POPF指令可以用来将修改后的标志加载到EFLAGS寄存器中。
  • 任务开关、POPF和IRET指令加载EFLAGS寄存器;因此,它们可以用来修改IF标志的设置。
  • 当一个中断通过中断门处理时,IF标志会被自动清除,这就禁止了可屏蔽的硬件中断。

屏蔽指令断点

EFLAGS寄存器中的RF(恢复)标志控制处理器对指令断点条件的响应。当设置时,它阻止指令断点产生调试异常(#DB);当清除时,指令断点将产生调试异常。RF标志的主要功能是防止处理器在以下情况下进入调试异常循环 。

切换堆栈时屏蔽异常和中断

为了切换到一个不同的堆栈段,软件经常使用一对指令,例如:
MOV SS, AX
MOV ESP, StackTop
如果在段选择器被加载到SS寄存器之后,但在ESP寄存器被加载之前,发生了中断或异常。ESP寄存器中,这两部分进入堆栈空间的逻辑地址在中断或异常处理过程中是不一致的。为了防止这种情况的发生,处理器在MOV到SS指令或POP到SS指令之后,处理器抑制中断、调试异常和单步陷阱异常,直到到达下一条指令后的指令边界。所有其他的故障仍然可以被产生。如果LSS指令被用来修改SS寄存器的内容(推荐的方法),这个问题就不会发生。

异常和中断的优先级

如果在一个指令边界有一个以上的异常或中断等待处理,处理器会以可预测的顺序处理它们。下表显示了异常和中断源类别之间的优先级。

image-20220410202420157

注意:虽然在表中列出的这些类别的优先级在整个架构中是一致的,但是每个类别中的例外情况是与实现有关的,可能因处理器不同而不同。处理器首先处理来自具有最高优先级的类的未决异常或中断,将执行转移到处理程序的第一条 指令。较低优先级的异常被丢弃;较低优先级的中断被搁置。当中断处理程序将执行返回到程序或任务中出现异常和/或中断的位置时,被丢弃的异常会重新产生。

中断描述符表

中断描述符表(IDT)将每个异常或中断向量与用于服务相关异常或中断的门描述符联系起来。与GDT和LDT一样,IDT是一个由8字节描述符组成的数组。。与GDT不同,IDT的第一个条目可以包含一个描述符。为了
为了形成对IDT的索引,处理器将异常或中断向量按8(门描述符的字节数)的比例进行调整。因为只有256个中断或异常向量,IDT不需要包含多于256个描述符。它可以包含少于256个描述符,因为描述符只需要用于可能发生的中断和可能出现的异常向量需要描述符。IDT中所有空的描述符槽都应该将描述符的当前标志设置为0。
IDT的基地址应该在8字节的边界上对齐,以最大限度地提高缓存行的性能 。极限值以字节为单位,并与基地址相加,得到最后一个有效字节的地址。极限值为0时,正好是一个有效的字节。因为IDT条目总是8个字节长,所以极限值应该是始终是8的整数倍(即8N-1)。
IDT可以驻留在线性地址空间的任何地方。如图6-1所示,处理器使用IDTR寄存器来定位IDT 。这个寄存器持有32位的基地址和16位的IDT限制。
LIDT(加载IDT寄存器)和SIDT(存储IDT寄存器)指令分别加载和存储IDTR的内容。LIDT指令将IDTR寄存器中的基地址和限值加载到一个内存操作数中。这条指令只有在CPL为0时才能被执行。它通常由操作系统的初始化代码在创建IDT时使用。操作系统也可以用它来改变一个IDT到另一个IDT。
SIDT指令将IDTR中存储的基数和极限值复制到内存中。这条指令可以在任何权限级别下执行。如果一个向量引用的描述符超过了IDT的限制,就会产生一个一般保护异常(#GP)。
注意
由于中断只传递给处理器内核一次,一个不正确配置的IDT可能导致不完整的中断处理和/或中断传递的阻塞。在设置IDTR基础/限制/访问字段和门描述符中的每个字段时,需要遵循IA-32架构的规则。

image-20220410202728708

IDT 描述符

IDT可能包含三种门描述符中的任何一种。

  • 任务门描述符
  • 中断门描述符

陷阱门描述符
图6-2显示了任务门、中断门和陷阱门描述符的格式。任务门的格式在IDT中使用的任务门的格式与在GDT或LDT中使用的任务门的格式相同。任务门包含一个异常和/或中断处理任务的TSS的段选择器。
中断和陷阱门与调用门非常相似。它们包含一个远指针(段选择器和偏移量),处理器用它来把程序的执行转移到异常或中断处理程序代码中的一个处理程序。
这些门的不同之处在于处理器处理EFLAGS寄存器中的IF标志的方式。

image-20220410205107225

中断与异常处理

处理器处理对异常处理程序和中断处理程序的调用的方式类似于处理对过程或任务的CALL指令来处理对过程或任务的调用。当响应一个异常或中断时,处理器使用异常或中断向量作为IDT中描述符的索引。如果该索引指向一个中断门或陷阱门,处理器调用异常或中断处理程序,其方式类似于调用门的CALL。如果 index 指向一个任务
门,处理器将执行一个任务切换到异常或中断处理任务,其方式类似于 CALL到一个任务门

异常或中断处理程序

中断门或陷阱门引用了一个异常或中断处理程序,该程序在当前执行的任务的上下文中运行(见图6-3)。该门的段选择器指向一个段描述符,该段描述符位于GDT或当前LDT中的一个可执行代码段。门描述符的偏移字段指的是
异常或中断处理程序的开头。

image-20220410205743923

当处理器执行一个对异常或中断处理程序的调用时。

  • 如果处理程序要在一个较低的权限级别上执行,就会发生堆栈切换。
    当堆栈切换发生时 :
    a. 处理程序使用的堆栈的段选择器和堆栈指针是从当前执行任务的TSS中获得的。在这个新的堆栈中,处理程序推送了被中断的堆栈段选择器和堆栈指针。
    b. 然后,处理器将EFLAGS、CS和EIP寄存器的当前状态保存在新的堆栈中(见图6-4)。
    c. 如果一个异常导致错误代码被保存,它将被推到EIP值之后的新栈上。
  • 如果处理程序要在与被中断程序相同的权限级别下执行。
    a. 处理器将EFLAGS、CS和EIP寄存器的当前状态保存在当前堆栈中(见图6-4)。
    b. 如果一个异常导致错误代码被保存,那么它将在EIP值之后被推到当前堆栈中。

image-20220410210127965

要从一个异常或中断处理程序中返回,处理程序必须使用IRET(或IRETD)指令。IRET指令与RET指令类似,只是它将保存的标志恢复到EFLAGS寄存器中。只有当CPL为0时,EFLAGS寄存器的IOPL字段才被恢复。

异常和中断处理程序的保护

异常和中断处理程序的特权级别保护与通过调用门调用普通程序的保护相似。处理器不允许将执行转移到一个异常或中断处理程序中。试图违反这一规则会导致一般保护异常(#GP)。异常处理程序和中断处理程序的保护机制在以下方面有所不同:

  • 因为中断和异常向量没有RPL,RPL在隐式调用异常和中断处理程序的隐式调用不检查RPL。
  • 只有在异常或中断产生的时候,处理器才会检查中断或陷阱门的DPL,如果有一个INT n, INT 3, 或 INTO 指令产生的异常或中断,处理器才会检查中断或陷阱门的 DPL。这里,CPL必须小于或等于门的DPL。这一限制防止了运行在权限级别3的应用程序或程序使用软件中断来访问关键的异常处理程序。中断来访问关键的异常处理程序,例如页面故障处理程序,条件是这些处理程序被放在更有权限的代码段中。对于硬件产生的中断和处理器检测到的异常,处理器忽略了中断和陷阱门的DPL。

由于异常和中断通常不会在可预测的时间发生,这些特权规则有效地对异常和中断处理程序可以运行的权限级别进行了限制。以下两种技术都可以用来避免违反权限级别:

  • 异常或中断处理程序可以放在一个符合要求的代码段中。这种技术可以用于处理程序,这些处理程序只需要访问堆栈上的数据(例如,划分错误异常)。如果处理程序需要来自数据段的数据,数据段需要从权限级别3访问,这将使其不受保护。
  • 处理程序可以被放置在一个特权级别为0的不符合要求的代码段中。这个处理程序将始终运行,不管被中断的程序或任务是在哪个CPL下运行。

异常或中断处理程序的标志用法

当通过中断门或陷阱门访问异常或中断处理程序时,处理器在将EFLAGS寄存器的内容保存在堆栈中后,清除EFLAGS寄存器中的TF标志。(在调用异常和中断处理程序时,处理器也会清除EFLAGS寄存器中的VM、RF和NT标志,然后将它们保存在堆栈中。)清除TF标志可以防止指令跟踪影响中断响应。A 后续的IRET指令将TF(以及VM、RF和NT)标志恢复到堆栈中EFLAGS寄存器的保存内容中的值。
中断门和陷阱门的唯一区别是处理器处理IF标志的方式。当通过中断门访问一个异常或中断处理程序时,处理器会清除IF标志以防止 其他中断干扰当前的中断处理程序。随后的IRET指令将IF标志恢复到堆栈上EFLAGS寄存器的保存内容中的值。通过陷阱门访问处理程序并不影响IF标志。

中断任务

当异常或中断处理程序通过IDT中的任务门被访问时,会产生一个任务切换。处理异常或中断的单独任务有几个优点。

  • 被中断的程序或任务的整个上下文被自动保存。
  • 一个新的TSS允许处理程序在处理异常或中断时使用一个新的权限级别0的堆栈。如果异常或中断发生时,当前权限级别0的堆栈被破坏,通过任务门访问处理程序可以通过为处理程序提供一个新的权限级别0的堆栈来防止系统崩溃。
  • 处理程序可以通过给它一个单独的地址空间来进一步与其他任务隔离。这可以通过以下方式实现给它一个单独的LDT。

用一个单独的任务来处理中断的缺点是,在任务切换时必须保存大量的机器状态,使得它比使用中断门要慢,从而导致中断延迟的增加。
IDT中的任务门引用GDT中的TSS描述符(见图6-5)。切换到处理程序任务的方式与普通任务切换相同。返回到被中断的任务的链接 被存储在处理程序任务的TSS的前一个任务链接域中。如果一个异常导致一个错误代码,这个错误代码被复制到新任务的堆栈中。
在操作系统中使用异常或中断处理任务时,实际上有两种机制可以用来调度任务:软件调度器(操作系统的一部分)和硬件调度器(处理器的中断机制的一部分)。软件调度器需要容纳中断任务当中断被激活时,可能会被调度。
注意
由于IA-32体系结构的任务不是可重入的,一个中断处理程序任务在它完成处理中断和执行IRET指令时,必须禁用中断。这个动作可以防止在中断任务的TSS仍被标记为忙时发生另一个中断,这将导致一般保护(#GP)异常。

image-20220411091420768

保护模式内存管理

内存管理概览

IA-32架构的内存管理设施分为两部分:分段和分页。
分段提供了一种隔离单个代码、数据和堆栈模块的机制,以便多个程序(或任务)可以在同一个处理器上运行而不互相干扰。分页提供了一种机制来实现传统的需求分页、虚拟内存系统,其中程序执行环境的部分被映射到物理内存中。分页也可以用来提供多个任务之间的隔离。
在保护模式下操作时,必须使用某种形式的分段。没有模式位可以禁用分段。然而,分页的使用是可选的。这两种机制(分段和分页)可以被配置为支持简单的单程序(或单任务)系统,或使用共享内存的多处理器系统。

image-20220403145257014

如图所示,分段提供了一种机制来划分处理器的可寻址内存空间(称为线性地址空间),分成更小的受保护的地址空间,称为段。分段可以可以用来保存程序的代码、数据和堆栈,或者保存系统数据结构(如TSS或LDT)。
如果一个处理器上有多个程序(或任务)在运行,每个程序可以被分配到它自己的段组。然后,处理器强制执行这些段之间的界限,并确保一个程序不会因为写进另一个程序的段而干扰程序的执行。分段机制还允许对段进行打字。

段落机制也允许段的类型化,这样可以限制对特定类型的段进行的操作。一个系统中的所有段都包含在处理器的线性地址空间中。要在一个特定的段中找到一个字节必须提供一个逻辑地址(也称为远指针)。

一个逻辑地址包括一个段选择器和一个偏移量。段选择器是一个段的唯一标识符。在其他方面,它提供了一个
在描述符表(如全局描述符表,GDT)中的偏移量,该数据结构称为段描述符。每个网段都有一个网段描述符,它指定了网段的大小,网段的访问权限和段的大小,段的访问权限和特权级别,段的类型,以及段的第一个字节在线性地址空间中的位置(称为段的基址)。逻辑地址的偏移部分被添加到段的基地址中,以定位段的第一个字节。
基准地址加上偏移量就形成了处理器线性地址中的一个线性地址
如果不使用分页,处理器的线性地址空间将直接被映射到处理器的物理地址空间。物理地址空间被定义为处理器可以在其地址总线上产生的地址范围。由于多任务计算系统通常定义的线性地址空间远远大于在物理内存中一次性包含的经济可行性,因此需要一些 “虚拟化 “线性地址空间的方法。这种线性地址空间的虚拟化是通过处理器的分页机制处理的。
分页支持 “虚拟内存 “环境,用少量的物理内存(RAM和ROM)和一些磁盘存储来模拟大的线性地址空间。当使用分页时,每个段被划分为若干页(通常每页大小为4KB),这些页存储在物理内存或磁盘上。操作系统或执行器维护一个页面目录和一组页面表,以跟踪这些页面。当一个程序(或任务)试图访问线性地址空间中的一个地址位置时,处理器会使用页目录和页表来将线性地址转换为物理地址,然后执行所要求的操作(读或写)在内存位置上。
如果被访问的页面当前不在物理内存中,处理器会中断程序的执行。(通过产生一个页面故障异常)。然后,操作系统或执行程序将该页从磁盘读入物理内存,并继续执行程序。
当分页在操作系统或执行系统中被正确实现时,物理内存和磁盘之间的换页对于程序的正确执行是透明的。即使是为16位IA32处理器编写的程序,在虚拟8086模式下运行时也可以进行分页(透明)。

linux下的内存管理

Linux系统中的物理存储空间和虚拟存储空间的地址范围分别都是从0x00000000到0xFFFFFFFF,共4GB,但物理存储空间与虚拟存储空间布局完全不同。Linux运行在虚拟存储空间,并负责把系统中实际存在的远小于4GB的物理内存根据不同需求映射到整个4GB的虚拟存储空间中。Linux主要工作在保护模式下。80X86从逻辑地址到物理地址变换中经过了两个阶段。第一阶段使用分段机制把程序的逻辑地址变换成处理器可寻址内存空间(称为线性地址空间)中的地址。第二阶段的分页机制把线性地址转换成物理地址。第一阶段的分段变换机制是必须使用的,但是第二阶段的分页机制是可选择的。如果没有开启分页机制,那么分段机制产生的线性地址空间就直接映射到处理器的物理地址空间上。

基本概念

物理地址: 放在寻址总线上的地址,用于内存芯片级内存单元寻址。放在寻址总线上,如果是读,电路根据这个地址每位的值就将相应地址的物理内存中的数据放到数据总线中传输。如果是写,电路根据这个地址每位的值就将相应地址的物理内存中放入数据总线上的内容。物理内存是以字节(8位)为单位编址的,是地址变换的最终结果地址,物理地址由32位或36位无符号整数表示。

逻辑地址:是指由程序产生的与段相关的偏移地址部分,每一个逻辑地址都由一个段和偏移量组成。在进行C语言指针编程中,可以读取指针变量本身值(&操作),实际上这个值就是逻辑地址,它是相对于你当前进程数据段的地址,不和绝对物理地址相干。只有在Intel实模式下,逻辑地址才和物理地址相等(因为实模式没有分段或分页机制,Cpu不进行自动地址转换);逻辑也就是在Intel 保护模式下程序执行代码段限长内的偏移地址(假定代码段、数据段如果完全一样)。

线性地址:是逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址,或者说是段中的偏移地址,加上相应段的基地址就生成了一个线性地址,是一个32位无符号整数,可以用来表示高达4GB的地址,也就是说,高达4294967296个内存单元,以十六进制表示,0x00000000到oxffffffff。如果启用了分页机制,那么线性地址可以再经变换以产生一个物理地址。若没有启用分页机制,那么线性地址直接就是物理地址。Intel 80386的线性地址空间容量为4G(2的32次方即32根地址总线寻址)。

虚拟内存:是指计算机呈现出要比实际拥有的内存大得多的内存量。因此它允许程序员编制并运行比实际系统拥有的内存大得多的程序。这使得许多大型项目也能够在具有有限内存资源的系统上实现。一个很恰当的比喻是:你不需要很长的轨道就可以让一列火车从上海开到北京。你只需要足够长的铁轨(比如说3公里)就可以完成这个任务。采取的方法是把后面的铁轨立刻铺到火车的前面,只要你的操作足够快并能满足要求,列车就能象在一条完整的轨道上运行。这也就是虚拟内存管理需要完成的任务。在现在操作系统中,都使用了MMU的存储管理技术,而MMU管理的地址是虚拟地址,虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存(一个连续完整的地址空间),而实际上,它通常是被分隔成多个物理内存碎片,还有部分暂时存储在外部磁盘存储器上,在需要时进行数据交换。与没有使用虚拟内存技术的系统相比,使用这种技术的系统使得大型程序的编写变得更容易,对真正的物理内存(例如RAM)的使用也更有效率。有时我们也把逻辑地址称为虚拟地址。因为和虚拟内存空间的概念类似,逻辑地址也是和实际物理内存容量无关的。

逻辑地址如何转换为线性地址

完整的内存管理,包含保护和地址变换两个关键部分。80386的工作模式包括实地址模式和虚地址模式(保护模式)。Linux主要工作在保护模式下。80X86从逻辑地址到物理地址变换中经过了两个阶段。第一阶段使用分段机制把程序的逻辑地址变换成处理器可寻址内存空间(称为线性地址空间)中的地址。第二阶段的分页机制把线性地址转换成物理地址。第一阶段的分段变换机制是必须使用的,但是第二阶段的分页机制是可选择的。如果没有开启分页机制,那么分段机制产生的线性地址空间就直接映射到处理器的物理地址空间上。

一个逻辑地址由两部份组成,段标识符: 段内偏移量。段标识符是由一个16位长的字段组成,称为段选择符。其中前13位是一个索引号。后面3位包含一些硬件细节,表示具体的是代码段寄存器还是栈段寄存器抑或是数据段寄存器,如图1所示。索引号就是“段描述符(segment descriptor)”的索引,段描述符具体地址描述了一个段。很多个段描述符,就组了一个数组,叫“段描述符表”,这样,可以通过段标识符的前13位,直接在段描述符表中找到一个具体的段描述符,这句话很关键,说明段标识符的具体作用,每一个段描述符由8个字节组成,如图2所示,与主题最密切的就是Base字段,她表示的是包含段的首字节的线性地址,也就是一个段的开始位置的线性地址。完全引用书中的一句话,一些全局的段描述符,就放在“全局段描述符表(GDT)”中,一些局部的,例如每个进程自己的,就放在所谓的“局部段描述符表(LDT)”中。那究竟什么时候该用GDT,什么时候该用LDT呢?这是由段选择符中的T1字段表示的,=0,表示用GDT,=1表示用LDT,GDT在内存中的地址和大小存放在CPU的GDTR控制寄存器中,而LDT则在IDTR寄存器中。这个过程中有几个基本的概念,一定要理清楚,如段选择符、段描述符、局部段描述符表、全局段描述符表。

image-20220403152513453

上图显示了一个逻辑地址是怎样转换成相应线性地址的,给定一个完整的逻辑地址[段选择符:段内偏移地址]

1、看段选择符的T1=0还是1,即先检查段选择符中的TI字段,以决定段描述符保存在哪一个描述符表中,知道当前要转换是GDT中的段(在这种情况下,分段单元从GDTR寄存器中得到GDT的线性基地址),还是LDT中的段(在这种情况下,分段单元从LDTR寄存器中得到GDT的线性基地址),再根据相应寄存器,得到其地址和大小。
2、由于一个段描述符是8字节长,因此她在GDT或LDT内的相对地址是由段选择符的最高13位的值乘以8得到,拿出段选择符中前13位,可以在这个数组中,查找到对应的段描述符,这样,它的Offset,即偏移地址就知道了。
3、把Base + offset,就是要转换的线性地址了。
对于软件来讲,原则上就需要把硬件转换所需的信息准备好,就可以让硬件来完成这个转换了。下图逻辑地址转换为线性地址实例,段选择符为0x7B,指向用户数据段,段起始地址为0x00000000,逻辑偏移地址为0x80495B0,最终的线性地址为Base + offset=0x80495B0。

image-20220403153532441

线性地址转物理地址

CPU通过地址来访问内存中的单元,地址有虚拟地址和物理地址之分,如果CPU没有MMU(Memory Management Unit,内存管理单元),或者有MMU但没有启用,CPU核在取指令或访问内存时发出的地址将直接传到CPU芯片的外部地址引脚上,直接被内存芯片(以下称为物理内存,以便与虚拟内存区分)接收,这称为物理地址(Physical Address,以下简称PA),如下图所示。

image-20220403155046532

如果CPU启用了MMU,CPU核发出的地址将被MMU截获,从CPU到MMU的地址称为虚拟地址(Virtual Address,以下简称VA),而MMU将这个地址翻译成另一个地址发到CPU芯片的外部地址引脚上,也就是将虚拟地址映射成物理地址,如下图所示

image-20220403155108029

虚拟内存地址和物理内存地址的分离,给进程带来便利性和安全性。虚拟地址必须和物理地址建立一一对应的关系,才可以正确的进行地址转换。

记录对应关系最简单的办法,就是把对应关系记录在一张表中。为了让翻译速度足够地快,这个表必须加载在内存中。不过,这种记录方式惊人地浪费。

因此,Linux采用了分页(paging)的方式来记录对应关系。所谓的分页,就是以更大尺寸的单位页(page)来管理内存。在Linux中,通常每页大小为4KB。

image-20220403155154004

依据以下步骤进行转换:

  1. 从cr3中取出进程的页目录地址(操作系统负责在调度进程的时候,把这个地址装入对应寄存器);
  2. 根据线性地址前十位,在数组中,找到对应的索引项,因为引入了二级管理模式,页目录中的项,不再是页的地址,而是一个页表的地址。(又引入了一个数组),页的地址被放到页表中去了。
  3. 根据线性地址的中间十位,在页表(也是数组)中找到页的起始地址;
  4. 将页的起始地址与线性地址中最后12位相加,得到最终我们想要的;

分段机制

由IA-32体系结构支持的分段机制可以用来实现各种各样的系统设计。这些设计的范围很广,从只极少使用分段的平面模型到保护。这些设计从扁平模型到多分段模型,这些模型采用分段来创建一个强大的操作环境,在其中多个程序和任务可以可靠地执行。

Basic Flat Model(基本平坦模型)

一个系统最简单的内存模型是基本的 “平坦模型”,在这个模型中,操作系统和应用程序可以访问一个连续的、没有分割的地址空间。在最大程度上,这种基本的平坦模型对系统设计者和应用程序都隐藏了架构的分割机制。
程序员为了实现IA-32体系结构的基本平坦内存模型,至少要创建两个段描述符,一个用于引用代码段,一个用于引用数据段。这两个段都被映射到整个线性地址空间:也就是说,两个段描述符都有同样的基址值为0,同样的段限制为4GBytes。通过设置段限制为4GBytes,分段机制就不会因为超出限制的内存引用而产生异常,即使在一个特定的地址上没有物理内存存在。ROM(EPROM)通常位于物理地址空间的顶部。因为处理器在FFF_FFF0H开始执行。RAM(DRAM)被放在物理地址空间的底部,因为复位初始化后DS数据段的初始基址是0。

image-20220403161325418

​ flat model

Protected Flat Model(受保护的平坦模型)

受保护的平坦模型与基本平坦模型类似,只是段的限制被设置为只包括物理内存实际存在的的地址范围(见下图)。一个一般保护的异常(#GP)会在任何访问不存在的内存的尝试中产生。这个模型提供了一个最低水平的
这种模式提供了最低水平的硬件保护,以防止某些类型的程序错误。

image-20220403161745702

​ Protected Flat Model

更多的复杂性可以被添加到这个受保护的平坦模型中,以提供更多的保护。例如,对于分页机制要在用户和主管的代码和数据之间提供隔离,需要定义四个段。用户的代码和数据段的权限级别为3,而主管的代码和数据段的权限级别为0。通常,这些段都是相互重叠的,并从线性地址空间的地址0开始。这种平坦的分段模型和一个简单的分页结构可以保护操作系统不受应用程序的影响。通过为每个任务或进程增加一个单独的分页结构,它还可以保护应用程序之间的相互影响。类似的设计被几个流行的多任务操作系统所采用。

Multi-Segment Model(多段模型)

多段模型(如下图)使用分段机制的全部功能,对代码、数据结构、程序和任务提供硬件强制保护。在这里,每个
程序(或任务)都有自己的段描述符表和自己的段。这些段可以是对其分配的程序来说是完全私有的,或者在程序之间共享。对所有程序段的访问以及对运行在各个程序上的执行环境都由硬件控制。
访问检查不仅可以用来防止引用一个段限制之外的地址,还可以防止在段内进行不允许的操作。例如,由于代码段被指定为只读段,所以可以用硬件来防止向代码段写东西。为段创建的访问权限信息也可以用来设置保护环或保护级别。保护级别可以用来保护操作系统程序免受应用程序的未经授权的访问。

image-20220403163121670

​ Multi-Segment Model

Segmentation in IA-32e Mode

在英特尔64架构的IA-32e模式下,分段的效果取决于处理器是在兼容模式还是64位模式下运行。在兼容模式下,分段的功能就像使用传统的16位或32位保护模式的语义。在64位模式下,分段功能通常被禁用(但不是完全禁用),创建一个平坦的64位线性地址空间。处理器将CS、DS、ES、SS的段基处理为零,创建一个线性地址,等于
有效地址。FS和GS段是个例外。这些段寄存器(存放段基)可以作为线性地址计算中的一个额外的基础寄存器。它们有助于寻址本地数据和某些操作系统的数据结构。注意,在64位模式下,处理器在运行时不执行段限制检查。

Paging and Segmentation(分页和分段)

分页可以与上图中描述的任何一种分段模式一起使用。处理器的分页机制将线性地址空间(段被映射到其中)分为若干页。然后这些线性地址空间的页被映射到物理地址空间的页中。分页机制提供了几个页级的保护设施,可以和段保护设施一起使用,也可以代替段保护设施。例如,它允许在逐页的基础上强制执行读写保护。分页 机制还提供了两级用户-监督者保护,也可以在每页的基础上指定。

逻辑地址和线性地址的转换

注:之前的内容为自己整理,以下为参考指导书翻译

在保护模式下的系统架构层面,处理器使用两个阶段的地址转换来获得物理地址:逻辑地址转换和线性地址空间分页。
物理地址:逻辑地址转换和线性地址空间分页。即使对段的使用降到最低,处理器地址空间中的每一个字节都可以用一个逻辑地址来访问。一个逻辑地址包括一个16位的段选择器和一个32位的偏移量。段选择器确定了字节所处的段,偏移量指定了字节在段中相对于该段的基址的位置。处理器将每个逻辑地址转化为一个线性地址。线性地址是处理器线性地址空间中的一个32位地址。像物理地址空间一样,线性地址空间是一个平面的(未分割的)。232字节的地址空间,地址范围从0到FFFFFFFH。线性地址空间包含所有段和为系统定义的系统表。为了将逻辑地址转换为线性地址,处理器做了以下工作:

  1. 使用段选择器中的偏移量来定位GDT或LDT中段的段描述符,并将其读入处理器。(只有当一个新的段选择器被加载到段寄存器中时才需要这个步骤。)
  2. 检查段描述符,以检查段的访问权限和范围,以确保段是可访问的,并且偏移量在段的限制范围内。
  3. 将段描述符中的段基地址加到偏移量上,形成一个线性地址。

如果不使用分页,处理器将线性地址直接映射到物理地址上。如果线性地址空间被分页,第二层的地址转换被用来将线性地址转换为物理地址。
image-20220404154555152

Logical Address Translation in IA-32e Mode(IA-32e 模式下的逻辑地址转换)

在 IA-32e 模式下,Intel 64 处理器使用上述步骤将逻辑地址转换为线性地址。在64位模式下,段的偏移量和基地址是64位而不是32位。线性地址地址格式也是64位宽,并受制于典型形式的要求。每个代码段描述符都提供一个L位。这个位允许一个代码段执行64位代码或传统的32位代码的代码段。

Segment Selectors(段选择子)

段选择器是一个段的16位标识符(见下图)。它并不直接指向段,而是指向定义该段的段描述符。一个段选择器包含以下内容 :

image-20220404154957115

​ Segment Selector

索引(第3至15位)- 在GDT或LDT中选择8192个描述符之一。处理器将索引值乘以8(段描述符中的字节数),并将结果加到GDT或LDT的基址上(分别来自GDTR或LDTR寄存器)。
TI(表指示器)标志
(Bit 2) - 指定要使用的描述符表:清除该标志选择GDT;设置该标志选择当前的LDT。

要求的权限级别(RPL)
(位0和1) - 指定选择器的权限级别。特权级别范围从0到3,其中0为最高权限级别。

GDT的第一个条目不被处理器使用。指向GDT这个条目的段选择器(即索引为0且TI标志设置为0的段选择器)被用作 “空段选择器”。就是说,一个索引为0且TI标志设置为0的段选择器被用作 “空段选择器”。当一个段寄存器(除了CS或SS寄存器)被载入空段选择器时,处理器不会产生一个异常。然而,当一个持有空段选择器的段寄存器被用来访问内存时,它会产生一个异常。空选择器可以用来初始化未使用的段寄存器。用一个空的段选择器加载CS或SS寄存器会导致一个通用的保护机制。段选择器加载CS或SS寄存器会产生一个通用保护异常(#GP)。段落选择器作为指针变量的一部分对应用程序是可见的,但是选择器的值通常是由链接编辑器分配或修改的,而不是应用程序。

Segment Registers(段寄存器)

image-20220404160315942

为了减少地址转换的时间和编码的复杂性,处理器提供了最多容纳6个段选择器的寄存器。这些段寄存器中的每一个都支持一种特定的内存引用(代码、堆栈或数据)。对于几乎任何一种程序的执行,至少要有代码段(CS),数据段(DS)和堆栈段(SS)寄存器且必须被加载有效的段选择器。处理器还提供了三个额外的数据段寄存器(ES、FS和GS),这些寄存器可以用来为当前执行的程序(或任务)提供额外的数据段。

一个程序要访问一个段,该段的段选择器必须被加载到其中一个段寄存器中。因此,尽管一个系统可以定义数以千计的段,但只有6个可以立即使用。其他的段可以通过在程序执行期间将它们的段选择器加载到这些寄存器中来实现。

每个段寄存器都有一个 “可见 “部分和一个 “隐藏 “部分。(隐藏部分有时被称为”描述符缓存 “或 “阴影寄存器”)。当段选择器被加载到段寄存器的可见部分时,处理器也会在段寄存器的隐藏部分加载基础地址、段限制和段描述符的访问控制信息。这些信息来自段选择器所指向的段描述符。缓存在段寄存器中的信息(可见的和隐藏的)允许处理器翻译地址,而不需要花费额外的总线周期来读取基址和限制。
系统中,多个处理器可以访问相同的描述符表,当描述符表被修改时,软件有责任重新加载段寄存器。如果不这样做,缓存在段寄存器中的旧的段描述符就可能在其内存驻留版本被修改后被使用。
为加载段寄存器提供了两种类型的加载指令:

  1. 直接加载指令,如MOV, POP, LDS, LES, LSS, LGS和LFS指令。这些指令明确地引用段寄存器。

  2. 隐含的加载指令,如CALL、JMP和RET指令的远端指针版本,SYSENTER和SYSEXIT指令,以及IRET、INTn、INTO和INT3指令。
    这些指令改变了CS寄存器的内容(有时也会改变其他段寄存器的内容),这是其操作的附带部分。MOV指令也可以用来将段寄存器的可见部分存储在通用寄存器中。

Segment Loading Instructions in IA-32e Mode(IA-32e模式下的段加载指令)

由于ES、DS和SS段寄存器在64位模式下不被使用,它们在段描述符寄存器中的字段(base, limit, and attribute)被忽略了。某些形式的段装载指令也是无效的(例如LDS, POP ES)。引用ES、DS或SS段的地址计算被视为段基
为零。
处理器检查所有线性地址引用都是典型的形式,而不是执行极限检查。模式切换并不改变段寄存器或相关描述符寄存器的内容。在64位模式执行过程中,这些寄存器也不会改变,除非执行显式段加载。
为了给应用程序设置兼容模式,段加载指令(MOV to Sreg, POP Sreg)在64位模式下正常工作。从系统描述符表(GDT或LDT)中读取一个条目,并加载到段描述符的隐藏部分。描述符寄存器的基数、极限和属性字段都被加载。然而,数据和堆栈段选择器以及描述符寄存器的内容被忽略。
当FS和GS段重写在64位模式下使用时,它们各自的基础地址被用于线性地址计算中使用。(FS或GS).base + index + displacement。然后,FS.base和GS.base会被扩展到整个实现所支持的线性地址大小。由此产生的有效地址计算可以跨越正负地址;产生的线性地址必须是规范的。
在64位模式下,使用FS段和GS段覆盖的内存访问不会被检查是否有运行时限制也不受属性检查的影响。正常的段加载(MOV to Sreg和POP Sreg)到FS和GS中加载一个在段描述符寄存器的隐藏部分加载一个标准的32位基础值。标准32位以上的基址位以上的基址位被清除为0,以保证使用少于64位的实现方式的一致性。
FS.base和GS.base的隐藏描述符寄存器字段被物理映射到MSR,以便加载64位实现支持的所有地址位。64位实现所支持的所有地址位。CPL=0的软件(特权软件)可以使用WRMSR将所有支持的线性地址位加载到FS.base或GS.base。写入64位FS.base和GS.base寄存器中的地址必须是典型的形式。如果WRMSR指令试图向这些寄存器写入非经典地址的WRMSR指令会导致#GP故障。
当处于兼容模式时,FS和GS的重写操作与32位模式行为的定义无关。值加载到隐藏描述符寄存器基字段的前32位线性地址位。兼容性模式在计算有效地址时忽略上面的32位。
一个新的64位模式指令,SWAPGS,可以用来加载GS base。SWAPGS将IA32_KernelGSbase MSR中的内核数据结构指针与GS base寄存器交换。然后,内核可以使用GS前缀对正常的内存引用来访问内核的数据结构。试图向IA32_KernelGSbase MSR写一个非正则的值(使用WRMSR)会导致一个#GP故障。

Segment Descriptors(段描述子)

image-20220404161935629

段描述符是GDT或LDT中的一个数据结构,为处理器提供段的大小和位置以及访问控制和状态信息。段落描述符通常是由编译器、链接器、加载器、操作系统或执行器,但不是应用程序创建的。

段落描述符中的标志和字段如下:

分段限制字段
指定段的大小。处理器把两个段限制字段放在一起,形成一个 一个20位的值。处理器以两种方式之一解释段限制,这取决于G(粒度)标志的设置:

  • 如果粒度标志是清除的,段的大小可以从1字节到1MByte,以字节为单位递增。
  • 如果颗粒度标志被设置,段的大小可以从4KB字节到4GB字节,以4KB字节为增量。

处理器以两种不同的方式使用段的限制,取决于段是一个向上扩展的段或一个向下扩展的段。对于扩大的段,
在逻辑地址中的偏移量可以从0到段的极限范围。大于段限制的偏移量产生一般保护异常(#GP,用于SS以外的所有段)或堆栈故障异常(#SS用于SS段)。对于向下扩展的段,段限具有相反的功能。
偏移量可以从段限加1到FFFFFFFH或FFFFFFH,取决于B标志的设置。小于或等于段限制的偏移量产生一般保护异常或堆栈故障异常。减少一个扩展段的段限值字段的值,在段的地址空间的底部分配新的内存,而不是在顶部。
IA-32架构的堆栈总是向下增长,使得这种机制对于可扩展堆栈。

基准地址字段
定义段的第0字节在4-GByte线性地址空间中的位置。处理器将三个基础地址字段放在一起,形成一个32位的数值。段的基址应与16字节的边界对齐,尽管16字节对齐不是必须的。这种对齐方式允许程序通过在16字节边界上对齐代码和数据来最大限度地提高性能。

类型字段

表示段或门的类型,并指定可以对该段进行的访问类型和增长方向。这个字段的解释取决于描述符类型标志指定的是应用(代码或数据)描述符还是系统描述符。类型字段的类型字段的编码对代码、数据和系统描述符是不同的。

S(描述符类型)标志
指定段描述符是用于系统段(S标志为清除)还是用于代码或数据段(S标志为设置)。
DPL(描述符权限级别)字段
指定段的权限级别。特权级别的范围是0到3,其中0是最高的级别。
P(段存在)标志
指示段是否存在于内存中(设置)或不存在(清除)。如果这个标志是清除的,当指向段描述符的段选择器出现时,处理器会产生一个段不存在的异常(#NP)。内存管理软件可以使用这个标志来控制哪些段在给定的时间内被实际加载到物理内存中。它为管理虚拟内存提供了一个除分页之外的控制。当该标志被清除时,操作系统或执行程序可以自由地使用标记为 “可用 “的位置来存储自己的数据,例如关于丢失的段的位置的信息。
D/B(默认操作大小/默认堆栈指针大小和/或上界)标志
执行不同的功能,取决于段描述符是否是可执行的代码段、扩展的数据段、或者是其他的段,一个扩展的数据段,或者一个堆栈段。(对于32位的代码和数据段,这个标志应该总是设置为1,对于16位的代码和数据段,这个标志应该设置为0)。

  • 可执行代码段。该标志被称为D标志,它指示了有效地址和操作数的默认长度。如果该标志被设置,32位的地址和32位或8位的操作数;如果它被清除,16位的地址和16位或8位操作数。指令前缀66H可以用来选择默认以外的操作数,而指令前缀67H可以用来选择一个非默认的地址大小。
  • 堆栈段(由SS寄存器指向的数据段)。该标志被称为B(大)标志。它指定了用于隐式堆栈操作的堆栈指针的大小(如push, pops, and calls)。如果该标志被设置,则使用一个32位的堆栈指针,该指针被存储在32位的ESP寄存器中;如果该标志被清除,则使用16位的堆栈指针,该指针被存储在16位的SP寄存器中。如果堆栈段被设置为一个向下扩展的数据段(在下一段中描述下一段描述),B标志也指定了堆栈段的上界。
  • 扩大-缩小数据段。该标志被称为B标志,它指定了段的上限。如果该标志被设置,上界是FFFFFFFH(4GB字节);如果该标志被清除,上限是FFFFFFFF(64KB)。

image-20220404164628034

描述符的分类

段描述符分类

image-20220404171152577

段描述符是GDT和LDT中的一个数据结构项,用于向处理器提供有关一个段的位置、大小以及访问控制的状态信息。每个段描述符的长度是8个字节,含有3个主要字段:

  • 段基地址
  • 段限长
  • 段属性

段描述符通常由编译器,链接器,加载器或者操作系统来创建,但绝不是应用程序。

段描述符通用格式如下所示

image-20220404170746133

系统段描述符中各个位的含义如下所示

image-20220404170802198

存储段描述符

数据段描述符

当S=1且TYPE字段的最高位(第2个双字的位11)为0时,表明是一个数据段描述符。

下图是数据段描述符的格式。

image-20220404171430725

代码段描述符

当S=1且TYPE字段的最高位(第2个双字的位11)为1时,表明是一个代码段描述符。

下图是代码段描述符的格式。

image-20220404171452192

系统描述符类型

当段描述符中S标志位(描述符类型)是复位状态(0)的话,那么该描述符是一个系统描述符。处理器能够识别以下一些类型的系统段描述符:

  • 局部描述符表(LDT)的段描述符
  • 任务状态段(TSS)描述符
  • 调用门描述符
  • 中断门描述符
  • 陷阱门描述符
  • 任务门描述符

这些描述符类型可分为两大类: 系统段描述符和门描述符。系统段描述符指向系统段(如LDT或TSS段),门描述符也就是一个”门”,对应调用、中断或陷阱门,其中含有代码段的选择符和段中程序入口点的指针;对于任务门,其中含有TSS的段选择符。

系统段描述符和门描述符类型字段的编码如下所示:

image-20220404170843601

x86系统架构概述

目录

[TOC]

系统级体系架构概述

image-20220328160624845

Global and Local Descriptor Tables(全局和局部描述符表)

​ 当在保护模式下操作时,所有的内存访问都要经过全局描述符表(GDT)或可选的本地描述符表(LDT),如图2-1所示。这些表包含的条目描述符称为段 。段描述符提供了段的基本地址以及访问权限、类型和使用信息。
​ 每个段描述符都有一个相关的段选择器。一个段选择器为使用它的软件提供了 一个GDT或LDT的索引(其相关段描述符的偏移量),一个全局/本地标志(决定选择器是否指向GDT或LDT),以及访问权限信息。
​ 要访问段中的一个字节,必须提供一个段选择器和一个偏移量。段选择器提供访问该段的段描述符(在GDT或LDT中)。从段描述符中,处理器获得该段在线性地址空间中的基本地址。然后,偏移量提供了字节相对于基址的位置。这种机制可以用来访问任何有效的代码、数据或堆栈段。只要该段可以从处理器所处的当前权限级别(CPL)访问。CPL被定义为当前执行的代码段的保护级别。
​ 见图2-1。图中的实心箭头表示一个线性地址,虚线表示一个段选择器。而点状箭头表示物理地址。为了简单起见,许多段选择器被显示为 直接指向一个段。然而,从段选择器到其相关段的实际路径总是通过GDT或LDT。GDT的基址的线性地址包含在GDT寄存器(GDTR)中;LDT的线性地址包含在LDT寄存器(LDTR)中。

Global and Local Descriptor Tables in IA-32e Mode

​ GDTR 和 LDTR 寄存器在 IA-32e 子模式(64 位模式和兼容模式)中都被扩展到 64 位宽。全局和局部描述符表在64位模式下被扩展以支持64位基地址,(16字节的LDT 描述符持有一个64位的基本地址和各种属性)。在兼容模式下,描述符不被扩展 。

System Segments, Segment Descriptors, and Gates(系统段,段描述符和门)

​ 除了构成程序或过程执行环境的代码、数据和堆栈段之外,架构还定义了两个系统段:任务状态段(TSS)LDT。GDT不被视为。
因为它不是通过段选择器和段描述符访问的。TSSs和LDTs有为它们定义了段描述符。该体系结构还定义了一组特殊的描述符,称为门[调用门(call gates),中断门(interrupt gates),陷阱门(trap gates),和 任务门(task gates)]。这些描述符为系统程序和处理程序提供了受保护的通道,这些程序和处理程序可能在与应用程序不同的权限级别上运行。例如,一个调用门的CALL可以提供访问一个代码段中的程序,该代码段与当前代码段处于相同或更低的权限级别(更多权限)。
​ 为了通过调用门访问一个过程,调用过程提供了调用门的选择器。然后,处理器对调用门进行访问权限检查,将CPL与调用门和调用门所指向的目标代码段的权限级别进行比较。如果对目标代码段的访问是允许的,处理器就会得到目标代码段的段选择器和该代码段的偏移。如果调用需要改变权限级别,处理器也会切换到目标权限级别的堆栈。新堆栈的段选择器是从当前运行任务的TSS中获得的。门也促进了16位和32位代码段之间的转换,反之亦然。

Gates in IA-32e Mode

在IA-32e模式下,以下描述符是16字节的描述符(扩大到允许64位基数)。LDT描述符、64位TSS、调用门、中断门和陷阱门。调用门促进了64位模式和兼容模式之间的转换。在IA32e模式下不支持任务门。在权限级别改变时,堆栈段选择器不从TSS中读取。相反,它们被设置为NULL。

Task-State Segments and Task Gates(任务状态段任务门)

​ TSS(见图2-1)定义了一个任务的执行环境的状态。它包括通用寄存器、段寄存器、EFLAGS寄存器、EIP寄存器和段选择器的状态-指向三个堆栈段(每个权限级别有一个堆栈)。TSS还包括段选择器 ,用于与任务相关的LDT和分页结构层次的基址。
​ 所有受保护模式下的程序执行都发生在一个任务(称为当前任务)的上下文中。
​ 当前任务的TSS的段选择器被存储在任务寄存器中。最简单的切换方法是调用或跳转到一个新的任务。这里,新任务的TSS的段选择器是在CALL或JMP指令中给出的。在切换任务时,处理器会执行以下动作:

1
2
3
4
5
1. 将当前任务的状态存储在当前TSS中。
2. 用新任务的段选择器加载任务寄存器。
3. 通过GDT中的段描述符访问新的TSS。
4. 将新任务的状态从新的TSS加载到通用寄存器、段寄存器中、LDTR,控制寄存器CR3(分页结构层次的基址),EFLAGS寄存器,以及EIP寄存器。
5. 开始执行新的任务。一个任务也可以通过一个任务门来访问。任务门类似于调用门,只是它提供了访问 (通过段选择器)访问一个TSS而不是一个代码段。

Task-State Segments in IA-32e Mode

在IA-32e模式下不支持硬件任务开关。然而,TSSs继续存在。TSS的基本地址由其描述符指定。一个64位的TSS持有以下对64位操作很重要的信息:

1
2
3
4
- 每个特权级别的堆栈指针地址
- 中断堆栈表的指针地址
- IO-permission位图的偏移地址(从TSS基数开始)。
在IA-32e模式下,任务寄存器被扩展为容纳64位基址。

Interrupt and Exception Handling(中断和异常处理)

​ 外部中断、软件中断和异常是通过中断描述符表(IDT)处理的。IDT存储了一个门描述符的集合,提供对中断和异常处理程序的访问。与 GDT一样,IDT不是一个段。IDT基础的线性地址包含在IDT寄存器(IDTR)中。IDT中的门描述符可以是中断、陷阱、或任务门描述符。要访问一个中断或异常处理程序 ,处理器首先从内部硬件、外部中断控制器或软件中接收一个中断向量(中断号)。中断控制器,或通过INT、INTO、INT 3或BOUND指令从软件接收一个中断向量(中断号)。中断向量 提供了一个进入IDT的索引。如果选择的门描述符是一个中断门或陷阱门,相关的处理程序就会被访问。处理程序的访问方式与通过调用门调用程序的方式类似。如果描述符是一个
任务门,处理程序将通过一个任务开关被访问。

Interrupt and Exception Handling IA-32e Mode

在IA-32e模式下,中断描述符被扩展到16个字节,以支持64位基本地址。IDTR寄存器被扩展为容纳64位基地址。不支持任务门。

Memory Management(内存管理)

​ 系统架构支持内存的直接物理寻址或虚拟内存(通过分页)。
​ 当使用物理寻址时,线性地址被当作物理地址处理。当使用分页时:所有的代码、数据、堆栈和系统段(包括GDT和IDT)可以被分页,只有最近访问的 页被保存在物理内存中。物理内存中的页面(有时称为页框)的位置包含在分页结构中。这些结构位于物理内存中。
​ 分页结构层次结构的基本物理地址包含在控制寄存器CR3中。分页结构中的条目决定了 一个分页框的物理地址、访问权限和内存管理信息。为了使用这种分页机制,一个线性地址被分解成几个部分。这些部分提供了进入分页结构和页框的单独偏移。一个系统可以有一个单一的分页结构层次,也可以有几个。例如 ,每个任务可以有自己的层次结构。

Memory Management in IA-32e Mode

在IA-32e模式下,物理内存页由一组系统数据结构管理。在兼容模式 和64位模式下,使用四级系统数据结构。这些结构包括 :

1
2
3
4
- 第4级页面映射(PML4)--PML4表中的一个条目包含了一个页面的基点的物理地址目录指针表、访问权限和内存管理信息。PML4的基本物理地址被存储在CR3中。
- 一组页目录指针表 - 页目录指针表中的一个条目包含了页目录指针表基的物理地址。
- 一组页目录 - 页目录表中的一个条目包含了一个页目录表基的物理地址、访问权限和内存管理信息。
- 成套的页表 - 一个页表中的条目包含了一个页框的物理地址,访问权限和内存管理信息。

System Registers(系统寄存器)

为了帮助初始化处理器和控制系统操作,系统结构在EFLAGS寄存器中提供了系统标志和几个系统寄存器:

1
2
3
4
5
6
7
- EFLAGS寄存器中的系统标志和IOPL字段控制任务和模式的切换,中断处理,指令跟踪和访问权限。
- 控制寄存器(CR0、CR2、CR3和CR4)包含各种控制系统级操作的标志和数据域。这些寄存器中的其他标志被用来表示对操作系统或执行器中特定处理器能力的支持。
- 调试寄存器允许设置断点以用于调试程序和系统软件。
- GDTR、LDTR和IDTR寄存器包含了它们各自表的线性地址和大小(限制)。
- 任务寄存器包含了当前任务的线性地址和TSS的大小。
- 特定型号的寄存器。这些寄存器控制一些项目,如调试扩展。
这些寄存器的数量和功能在英特尔64和IA-32处理器系列的不同成员中是不同的。

System Registers in IA-32e Mode

​ 在IA-32e模式下,四个系统描述符表寄存器(GDTR、IDTR、LDTR和TR)在硬件上被扩展为
以容纳64位的基本地址。EFLAGS成为64位的RFLAGS寄存器。CR0-CR4被扩展到64位。CR8变得可用。CR8提供了对任务优先级寄存器(TPR)的读写访问,这样操作系统就可以控制外部设备的优先级。在64位模式下,调试寄存器DR0-DR7为64位。在兼容模式下,DR0-DR3的地址匹配也是以64位粒度进行的。在支持IA-32e模式的系统上,扩展功能启用寄存器(IA32_EFER)是可用的。这个特定型号的寄存器控制IA-32e模式的激活和其他IA-32e模式的操作。此外,还有几个特定型号的寄存器管理 IA-32e 模式指令。

1
2
3
4
- IA32_KernelGSbase - 由 SWAPGS 指令使用。
- IA32_LSTAR - 由 SYSCALL 指令使用。
- IA32_SYSCALL_FLAG_MASK - 由SYSCALL指令使用。
- IA32_STAR_CS - 由SYSCALL和SYSRET指令使用。

Other System Resources

除了前几节描述的系统寄存器和数据结构,系统结构还提供了以下的额外资源。

1
2
3
4
- 操作系统指令
- 性能监测计数器
- 内部缓存和缓冲区

实模式和保护模式转换

二者根本区别为:进程内存受保护与否

保护模式 - 这是处理器的原生操作模式。它提供了一套丰富的结构特性、灵活性、高性能和对现有软件基础的向后兼容性。

真实地址模式 - 这种操作模式提供了英特尔8086处理器的编程环境,并有一些扩展(如切换到受保护或系统管理模式的能力)。

实模式工作原理

实模式出现于早期8088CPU时期。当时由于CPU的性能有限,一共只有20位地址线(所以地址空间只有1MB),以及8个16位的通用寄存器,以及4个16位的段寄存器。所以为了能够通过这些16位的寄存器去构成20位的主存地址,必须采取一种特殊的方式。当某个指令想要访问某个内存地址时,它通常需要用下面的这种格式来表示:

1
(段基址:段偏移量)

其中第一个字段是段基址,它的值是由段寄存器提供的。

第二字段是段内偏移量,代表你要访问的这个内存地址距离这个段基址的偏移。它的值就是由通用寄存器来提供的,所以也是16位。

CPU采用把段寄存器所提供的段基址先向左移4位。这样就变成了一个20位的值,然后再与段偏移量相加,即可组合成一个二十位的地址。即:

1
物理地址 = 段基址<<4 + 段内偏移

保护模式工作原理

随着CPU的发展,CPU的地址线的个数也从原来的20根变为现在的32根,所以可以访问的内存空间也从1MB变为现在4GB,寄存器的位数也变为32位。所以实模式下的内存地址计算方式就已经不再适合了。所以就引入了现在的保护模式,实现更大空间的,更灵活也更安全的内存访问。

在保护模式下,CPU的32条地址线全部有效,可寻址高达4G字节的物理地址空间; 但是我们的内存寻址方式还是得兼容老办法,即(段基址:段偏移量)的表示方式。当然此时CPU中的通用寄存器都要换成32位寄存器(除了段寄存器)来保证寄存器能访问所有的4GB空间。

我们的偏移值和实模式下是一样的,就是变成了32位而已,而段值仍旧是存放在原来16位的段寄存器中,但是这些段寄存器存放的却不再是段基址了,毕竟之前说过实模式下寻址方式不安全,我们在保护模式下需要加一些限制,而这些限制可不是一个寄存器能够容纳的,于是我们把这些关于内存段的限制信息放在一个叫做全局描述符表(GDT)的结构里。全局描述符表中含有一个个表项,每一个表项称为段描述符。而段寄存器在保护模式下存放的便是相当于一个数组索引的东西,通过这个索引,可以找到对应的表项。段描述符存放了段基址、段界限、内存段类型属性(比如是数据段还是代码段,注意一个段描述符只能用来定义一个内存段)等许多属性,具体信息见下图:

image-20220328193206147

其中,段界限表示段边界的扩张最值,即最大扩展多少或最小扩展多少,用20位来表示,它的单位可以是字节,也可以是4KB,这是由G位决定的(G为1时表示单位为4KB)。

实际段界限边界值=(描述符中的段界限+1)*(段界限的单位大小(即字节或4KB))-1,如果偏移地址超过了段界限,CPU会抛出异常。

全局描述符表位于内存中,需要用专门的寄存器指向它后, CPU 才知道它在哪里。这个专门的寄存器便是GDTR(一个48位的寄存器),专门用来存储 GDT 的内存地址及大小。

还需要介绍一个新的概念:段的选择子。段寄存器 CS、 DS、 ES、 FS、 GS、 SS,在实模式下时,段中存储的是段基地址,即内存段的起始地址。 而在保护模式下时,由于段基址已经存入了段描述符中,所以段寄存器中再存放段基址是没有意义的,在段寄存器中存入的是一个叫作选择子的东西。选择子“基本上”是个索引值。由于段寄存器是 16 位,所以选择子也是 16 位,在其低 2 位即第 0~1 位, 用来存储 RPL,即请求特权级,可以表示 0、 1、 2、 3 四种特权级。在选择子的第 2 位是 TI 位,即 Table Indicator,用来指示选择子是在 GDT 中,还是 LDT 中索引描述符。 TI 为 0 表示在 GDT 中索引描述符, TI 为 1 表示在 LDT 中索引描述符。选择子的高 13 位,即第 3~15 位是 描述符的索引值,用此值在 GDT 中索引描述符。前面说过 GDT 相当于一个描述符数组,所以此选择子中的索引值就是 GDT 中的下标。选择子结构如下:

image-20220328193601767

此外, 扩充的存储器分段管理机制和可选的存储器分页管理机制,不仅为存储器共享和保护提供了硬件支持,而且为实现虚拟存储器提供了硬件支持; 支持多任务,能够快速地进行任务切换(switch)和保护任务环境(context); 4个特权级和完善的特权检查机制,既能实现资源共享又能保证代码和数据的安全和保密及任务的隔离; 支持虚拟8086方式,便于执行8086程序。

实模式到保护模式的切换

从实模式切换到保护模式大致可以分为以下几个步骤:

1
2
3
4
5
6
7
8
9
1、屏蔽中断

2、初始化全局描述符表(GDT)

3、将CR0寄存器最低位置1

4、执行远跳转

5、初始化段寄存器和栈指针

屏蔽中断

在16位实模式下的中断由BIOS处理,进入保护模式后,中断将交给中断描述符表IDT里规定的函数处理,在刚进入保护模式时IDTR寄存器的初始值为0,一旦发生中断(例如BIOS的时钟中断)就将导致CPU发生异常,所以需要首先屏蔽中断。屏蔽中断可以使用cli指令:

1
cli

初始化GDT

在32位保护模式中,段与段之间是互相隔离的,当访问的地址超出段的界限时处理器就会阻止这种访问,因此每个段都需要有起始地址、范围、访问权限以及其他属性四个部分,这四个部分合在一起叫做段描述符(Segment Descriptor),总共需要8个字节来描述。但Intel为了保持向后兼容,将段寄存器仍然规定为16-bit,显然我们无法用16-bit的段寄存器来直接存储64-bit的段描述符。

解决的办法是将所有64-bit的段描述符放到一个数组中,将16-bit段寄存器的值作为下标来访问这个数组(以字节为单位),获取64-bit的段描述符,这个数组就叫是全局描述符表

将CR0最低位置1

CR0是系统内的32位控制寄存器之一,可以控制CPU的一些重要特性。其中最低位是保护允许位(Protected Mode Enable, PE),PE位置1后CPU进入保护模式(注意此时还是16位保护模式,不是32位保护模式),置0时则为实模式。现在我们要进入保护模式,即将CR0的最低位置1,汇编代码如下:

1
2
3
4
-把 cr0 的最低位置为 1,开启保护模式
mov eax, cr0
or eax, 0x1
mov cr0, eax

执行远跳转

将cr0最低位置1后,CPU就进入了保护模式,此时需要马上执行一条远跳转指令:

1
jmp 08h:PModeMain

这条指令有两个作用,第一个作用是将cs段寄存器的值修改为08h,切换到保护模式后,CPU寻址的方式就从实模式中的段地址 * 16 + 偏移地址改为了通过gdt寻址,所以这里的08h是段选择子而不是段地址,并且远跳转指令会自动将cs的值修改为对应的段选择子,这里是08h。

远跳转的另一个作用是清空CPU的流水线,流水线的作用在计组中有提到过,为了加速指令的执行,CPU在执行当前指令时会同时加载并解析接下来的一些指令,在进入保护模式之前,已经有许多指令进入了流水线,这些指令都是按16位模式处理的,而进入保护模式后的指令都是32位,所以这里通过一个远跳转来让CPU清空流水线。

切换到32位模式后,就应该执行32位的指令了,所以从PModeMain开始的指令都采用32位模式编译,通过[bits 32]这个标记实现:

1
2
[bits 32]
PModeMain:

初始化段寄存器和栈指针

上一步中我们将代码段寄存器cs初始化成了0x08,现在我们还需要初始化其他的段寄存器如数据段寄存器ds,拓展段寄存器es,栈段ss以及fs,gs两个由操作系统使用的段。

另外我们还需要初始化栈指针ebp和esp,代码如下:

1
2
3
4
5
6
7
8
9
10
11
[bits 32]
PModeMain:
mov ax, 0x10 ; 将数据段寄存器ds和附加段寄存器es置为0x10
mov ds, ax
mov es, ax
mov fs, ax ; fs和gs寄存器由操作系统使用,这里统一设成0x10
mov gs, ax
mov ax, 0x18 ; 将栈段寄存器ss置为0x18
mov ss, ax
mov ebp, 0x7c00 ; 现在栈顶指向 0x7c00
mov esp, ebp

需要修改的内容

  • GDT初始化:定义段描述符、定义GDTR的数据结构、定义GDT选择子

  • 数据段+堆栈段

  • 16位代码段(实模式下)的定义

    1
    2
    3
    4
    5
    6
    7
    1.设置代码运行环境,即给相关寄存器赋值;
    2.初始化16位代码段描述符 + 32位代码段描述符 + 堆栈段描述符 +数据段描述符;
    3.初始化全局描述符表寄存器GDTR的内容,因为其基地址还没有初始化, 然后通过lgdt [GdtPtr],将内存中GDTR的内容加载到GDTR中,重点在于保存 GDT的基地址;
    4.关中断, 即设置CPU不响应任何其他的外部中断,因为CPU现在的时间片只属于当前加载的程序;
    5.打开地址线A20;
    6将CR0的 PE 位置1;PE位==1,表明CPU运行在保护模式下;
    7.跳转到保护模式: jmp dword SelectorCode32:0 ,这里的代码指提供了选择子,(2.3)末部分,已经说明了为什么通过选择子就可以索引到 32位代码段 LABEL_SEG_CODE32;(这就是从实模式跳入保护模式)
  • 32位代码段(由实模式跳入,即保护模式)的定义

    1
    2
    3
    1.将对应选择子赋值到 对应寄存器, 即设置任务代码的运行环境,不得不提的是本段代码还改变了ss和esp,则在32位代码段中所有的堆栈操作将会在新增的堆栈段中进行;
    2.做任务;
    3.任务做完后,跳转到16位代码段,因为从保护模式跳回实模式,只能从16位代码段中跳回;

80x86系统指令寄存器

标志寄存器

image-20220328194436597

  EFLAGS系统标志和IOPL字段控制I/O,可屏蔽的硬件中断、调试、任务切换和虚拟8086模式。仅允许特权代码(通常为操作系统过执行代码)修改这些位。

​ 在64位模式下,RFLAGS寄存器扩展为64位,保留高32位。PFLAGS中系统标志(64位模式)或EFLAGS(兼容模式)。在IA-32e模式下,处理器不允许设置VM位,因为不支持virtual-8086模式(尝试设置该位将被忽略)。同样,处理器将不会设置NT位。但是处理器确实允许软件将NT位置1(请注意,如果将NT位置1,则IRET会在IA-32e模式下引起一般性保护故障)。在IA-32e模式下,YSCALL/SYSRET指令具有一种可编程的方法来指定哪些位是已RFLAGS/EFLAGS中清除。这些说明保存/恢复EFLAGS/RFLAGS。

内存管理寄存器

image-20220328194633100

GDTR

保存基地址(在保护模式下为32位,在IA-32e模式下为64位)和16位表GDT的限制。基地址指定GDT字节0的线性地址;表格限制指定了表中的字节数。LGDT和SGDT指令分别加载和存储GDTR寄存器。开机或重置在处理器中,基地址设置为默认值0,限制设置为0FFFFH。必须有新的基本地址将其作为保护模式操作的处理器初始化过程的一部分加载的GDTR。

LDTR

​ 保留16位段选择器的结伴地址(在保护模式下为32位,在IA-32e模式下为64位)段限制和LDT的描述符属性。基地址指定字节的线性地址LDT段的0,段限制指定段中的字节数。LLDT和SLDT指令分别加载和存储LDTR寄存器的段选择器部分的包含LDT的段必须在GDT中具有段描述符。当LLDT指令加载一个LDTR中的段选择器:LDT描述符中的基地址、限制和描述符属性会自动加载到LDTR中。
​ 发生任务切换时,LDTR会自动加载LDT的段选择器和描述符为新任务。在写入新的LDT信息之前,不会自动保存LDTR的内容进入寄存器。在处理器加电或重置时,段选择器和基地址被设置为默认值0和限制设置为0FFFFH。

IDTR

​ 寄存器保存基地址(保护模式下为32位,IA-32e模式下为64位)和16位表限制IDT。基地址指定IDT字节0的线性地址,表限制指定数量表中的字节数。LIDT和SIDT指令分别加载和存储IDTR寄存器。开机或重置处理器后,基地址设置为默认值0,限制设置为0FFFFH。然后可以在处理器初始化过程中更改寄存器中的地址和限制。

TR

​ 任务寄存器包含16位段选择器,基地址(在保护模式下为32位,在IA-32e中为64位),段限制和当前任务的TSS的描述符属性。选择器引用TSS、GDT的描述符。基地址指定TSS字节0的线性地址;段限制指定TSS中的字节数。LTR和STR指令分别加载和存储任务寄存器的段选择器部分。当LTR指令将段选择器加载到任务寄存器中时,基址、限制和描述符属性从TSS描述符将自动加载到任务寄存器中。处理器加电或重置时,基地址设置为默认值0,限制设置为0FFFFH。发生任务切换时,任务寄存器会自动加载段选择器和描述符新任务的TSS。在写入的新的TSS之前,不会自动保存任务寄存器的内容信息进去寄存器。

控制寄存器

CR0

包含控制处理器的操作模式和状态的系统控制标志。

CR3

包含分页结构层次结构基础的物理地址和两个标志(PCD和PWT)。仅指定基址的最高有效位(减去低12位);低12位地址“0”假定为0.因此,第一个分页结构必须与页面(4KB)对齐边界。PCT和PWT标志控制处理器内部数据中该分页结构的缓存(它们不控制页面目录信息的TLB缓存)。使用物理地址扩展中,CR3寄存器包含页面目录指针表的基地址。在IA-32e模式下,CR3寄存器包含PML4表的基地址。

系统指令

LGDT加载GDTR寄存器——将GDT基址和限制从内存加载到GDTR寄存器。
SGDT存储GDTR寄存器——将GDT基址和GDTR寄存器中的限制存储到内存。
LIDT加载IDTR寄存器——将IDT基址和限制从存储器加载到IDTR寄存器中。
SIDT加载IDTR寄存器——将IDT寄存器的IDT基址和限制存储到内存中。
LLDT加载LDT寄存器——将LDT段选择器和段描述符从内存加载到LDTR,段选择器操作数也可以位于通用寄存器中。
SLDT存储LDT寄存器——将LDTR寄存器中的LDT段选择器存储到存储器或存储器中。
LTR记载任务寄存器——将TSS的段选择器和段描述符从内存加载到任务寄存器,段选择器操作数也可以位于通用寄存器中。
STR存储任务寄存器——将当前任务TSS的段选择器从任务存储器存储到存储器或通用寄存器。

鸣谢

1
2
3
https://zhuanlan.zhihu.com/p/42309472
https://mp.weixin.qq.com/s/VGhpbZaeyVwq3Ghs2E6eEw
https://zhuanlan.zhihu.com/p/412845339

解决广告弹窗

对于广告弹窗,我们采取安装火绒安全软件的方式来解决。具体流程如下

打开网站

1
https://www.huorong.cn/

image-20220312201421955

点击上方一栏的个人产品

image-20220312201439903

点击免费下载

下载安装等步骤正常进行。

安装好之后如下

image-20220312201528490

点击安全工具

点击右上方的弹窗拦截

image-20220312201548894

注:首次点击需要应该需要下载,为正常现象。

到此工作完成。

注:完成之后建议把其他杀毒软件全部卸载。

中文

点击率(CTR)的预测在网络广告中至关重要[McMahan等人,2013[1];Juan等人,2016[2];Wen等人,2019[3]],其中的任务是估计用户点击推荐广告或物品的概率。在在线广告中,广告商向出版商付费,在出版商的网站上展示他们的广告。一种流行的支付模式是每次点击成本(CPC)模式[Zhou等人,2018[4];Zhou等人,2019[5]],广告商只有在点击发生时才会被收费。因此,出版商的收入在很大程度上依赖于准确预测CTR的能力[Wang等人,2017[6]] 。

如今,各种CTR模型层出不穷,从 Linear到 TreeBased ,再到Embedding和MLP,随着深度学习网络的推进,CTR模型也得到了充分的发展。每个模型都有其优点,例如自适应因子化网络(AFN)可以从数据中自适应地学习任意等级的交叉特征,双输入感知因式分解机(DIFM)能在矢量级有效地学习输入感知因子(用于重新加权原始特征表示)。但是CTR预测的情况总是多种多样,有时我们会面临大量的用户数据需要快速处理,有时又会缺乏用户历史信息而面临冷启动的问题。没有一种CTR模型会很好地适应所有的情况。

基于自动机器学习的启发,我们将创建一个CTR库,里面包含着目前世界上表现优异的各种CTR模型。主要根据预测时所面临的情况,根据传入的参数,来自适应地判断并且选择适当的CTR模型进行预测,以此来提高预测精度,缩短预测时间,最大化企业效率。

[1] [McMahan et al., 2013] H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. Ad click prediction: a view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1222–1230. ACM, 2013.

[2] [Juan et al., 2016] Yuchin Juan, Yong Zhuang, Wei-Sheng Chin, and Chih-Jen Lin. Field-aware factorization machines for ctr prediction. In Proceedings of the 10th ACM Conference on Recommender Systems, pages 43–50. ACM, 2016.

[3] [Wen et al., 2019] Hong Wen, Jing Zhang, Quan Lin, Keping Yang, and Pipei Huang. Multi-level deep cascade trees for conversion rate prediction in recommendation system. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 338–345, 2019

[4] [Zhou et al., 2018] Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1059–1068. ACM, 2018.

[5] [Zhou et al., 2019] Guorui Zhou, Na Mou, Ying Fan, Qi Pi, Weijie Bian, Chang Zhou, Xiaoqiang Zhu, and Kun Gai. Deep interest evolution network for click-through rate prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5941–5948, 201

[6] [Wang et al., 2017] Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. Deep & cross network for ad click predictions. In Proceedings of the ADKDD’17, page 12. ACM, 2017.

英文

The prediction of click-through rate (CTR) is crucial in online advertising [McMahan et al., 2013[1]; Juan et al., 2016[2]; Wen et al., 2019[3]], where the mission is to estimate the probability that users click on a recommended ad or item. In online advertising, advertisers pay publishers to display their ads on publishers’ sites. One popular payment model is the cost-per-click (CPC) model [Zhou et al., 2018[4]; Zhou et al., 2019[5]], where advertisers are charged only when a click occurs. As a consequence, a publisher’s revenue relies heavily on the ability to predict CTR accurately [Wang et al., 2017[6]].

Nowadays, various CTR models have emerged, from Linear to TreeBased , to Embedding and MLP. With the advancement of deep learning networks, the CTR model has also been fully developed. Each model has its merits. For Instance, Adaptive Factorization Network (AFN) can adaptively learn cross features of any level from data, and Dual Input Perceptual Factorization Machine (DIFM) can effectively learn input perception factors at vector level (used to reweight original feature representations). Nevertheless, there are always various situations for CTR prediction. We are faced with a large amount of user data that needs to be processed quickly at times, and a cold boot due to the lack of user history information at others. There is no CTR model that fits well in all situations.

Inspired by automated machine learning, we will create a CTR library containing a variety of CTR models that are currently performing well in the world. Based on the incoming parameters, we will self-adaptively determine and select the appropriate CTR model for forecasting according to the situation, in order to improve forecasting accuracy, shorten forecasting time, and maximize business efficiency.

[1] [McMahan et al., 2013] H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. Ad click prediction: a view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1222–1230. ACM, 2013.

[2] [Juan et al., 2016] Yuchin Juan, Yong Zhuang, Wei-Sheng Chin, and Chih-Jen Lin. Field-aware factorization machines for ctr prediction. In Proceedings of the 10th ACM Conference on Recommender Systems, pages 43–50. ACM, 2016.

[3] [Wen et al., 2019] Hong Wen, Jing Zhang, Quan Lin, Keping Yang, and Pipei Huang. Multi-level deep cascade trees for conversion rate prediction in recommendation system. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 338–345, 2019

[4] [Zhou et al., 2018] Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1059–1068. ACM, 2018.

[5] [Zhou et al., 2019] Guorui Zhou, Na Mou, Ying Fan, Qi Pi, Weijie Bian, Chang Zhou, Xiaoqiang Zhu, and Kun Gai. Deep interest evolution network for click-through rate prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5941–5948, 201

[6] [Wang et al., 2017] Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. Deep & cross network for ad click predictions. In Proceedings of the ADKDD’17, page 12. ACM, 2017.

CTR各模型优劣总结

前言

本文是依照上一篇文章的顺序来进行整理,现附上上一篇链接

1
https://perfect-player.github.io/2021/09/27/CTR/

本文参考原论文(主)与网络资料(次)编写而成。

Convolutional Click Prediction Model(卷积点击预测模型CCPM)

由于循环神经网络在连续广告印象上的不可改变的传播方式,在有效建模动态点击预测方面有局限性,而深度CNN架构的池化和卷积层可以从连续的广告印象中充分提取局部-全局的关键特征。

CCPM就是基于CNN的一个架构,CCPM可以从具有不同元素的输入实例中提取局部-全局关键特征,这不仅可以针对单个广告印象,也可以针对连续的广告印象。

1
2
原文表述
CCPM can extract local-global key features from an input instance with varied elements, which can be implemented for not only single ad impression but also sequential ad impression.

Factorization-supported Neural Network(因子分解支持的神经网络FNN)

出发点

1
2
3
1.之前运用的CTR模型大多是线性的,都是基于大量的稀疏特征的编码。性能相对较低,因为在学习非微观模式时,无法捕捉到假定的(有条件的)独立原始特征之间的相互作用。
2.当时的非线性模型不能利用所有可能的不同特征的组合。
3.大多数预测模型有浅层的结构,对复杂的海量数据的基础模型表达有限,数据建模和泛化能力仍然受到限制。

基于上述出发点引入了深度学习模型。

带有监督学习嵌入层的FNN使用因子化机器被提出来,以有效地减少从稀疏特征到密集的连续特征。

1
2
原文表述
Specifically,FNN with a supervised-learning embedding layer using factorisation machines is proposed to efficiently reduce the dimension from sparse features to dense continuous features.

Product-based Neural Network(PNN)

背景

1
深度神经网络(DNNs)在分类和回归任务中显示了巨大的能力,在用户反应预测中采用DNNs是很有前途的。之前为了改善多领域分类数据的交互,提出的一种基于因子预训练的方法,基于串联的嵌入向量,构建多层感知器(MLPs)来探索特征的相互作用。嵌入初始化的质量在很大程度上受到因式分解机的限制。

为了利用神经网络的学习能力和挖掘以一种比MLPs更有效的方式挖掘数据的潜在模式,所以提出PNN。PNN有望在多领域的分类数据上学习高阶潜在模式。

1
2
3
原文表述
To utilize the learning ability of neural networks and mine the latent patterns of data in a more effective way than MLPs,in this paper we propose Product-based Neural Network。
PNN is promising to learn high-order latent patterns on multi-field categorical data.

Wide & Deep

谷歌曾经的主流推荐模型,业界影响巨大。

1
记忆能力:可以被理解为模型直接学习并利用历史数据中物品和特征的“共现频率”的能力

提出动机

1
利用手工构造的交叉组合特征来使线性模型具有记忆性会得到一个不错的效果,但特征工程需要耗费大量精力,对于未曾出现过的特征组合,权重系数为0,无法进行泛化。
1
2
线性模型,记忆力较强,但泛化能力弱
embedding模型,记忆能力弱,泛化能力强

基于优势互补,提出Wide & Deep,左边Wide部分是一个简单的线性模型,右边Deep部分是一个经典的DNN模型。

WDL的深层部分将稀疏的特征嵌入连接起来作为MLP的输入,宽层部分使用手工制作的特征作为输入。深度部分和宽度部分的对数相加,得到预测概率。

1
2
原文表述
WDL’s deep part concatenates sparse feature embeddings as the input of MLP,the wide part use handcrafted feature as input. The logits of deep part and wide part are added to get the prediction probability.

DeepFM

整合了FM和深度神经网络(DNN)的架构。它像FM一样对低阶特征的交互进行建模,像DNN一样对高阶特征的交互进行建模。不同于

Wide & Deep,DeepFM可以在没有任何特征工程的情况下进行端到端训练。但复杂性较大。

优点

1
2
3
1.它不需要任何预训练
2.它同时学习高阶和低阶特征的相互作用;
3.它引入了特征嵌入的共享策略以避免特征工程

原文表述

1
2
3
1) it does not need any pre-training; 
2) it learns both high- and loworder feature interactions;
3) it introduces a sharing strategy of feature embedding to avoid feature engineering

DeepFM可以看作是WDL和FNN的改进。与WDL相比,DeepFM在广义部分使用FM而不是LR,在深义部分使用嵌入向量的连接作为MLP的输入。与FNN相比,FM的嵌入向量和MLP的输入是相同的。而且它们不需要FM预训练向量来初始化,它们是端对端学习。

1
2
原文表述
DeepFM can be seen as an improvement of WDL and FNN.Compared with WDL,DeepFM use FM instead of LR in the wide part and use concatenation of embedding vectors as the input of MLP in the deep part. Compared with FNN,the embedding vector of FM and input to MLP are same. And they do not need a FM pretrained vector to initialiaze,they are learned end2end.

Piece-wise Linear Model

背景

1
CTR预测问题是一个高度非线性的问题。LR很难抓住非线性因素,基于树的方法不适合非常稀疏和高维的数据,FM不能适应数据中所有的一般非线性模式

提出了一个用于大规模数据的片状线性模型及其训练算法LS-PLM,遵循分而治之的策略。首先将特征空间划分为几个局部区域,然后在每个区域内拟合一个线性模型。结果是输出加权线性预测的组合。它可以从稀疏数据中捕捉到稀疏数据中的非线性模式,并将我们从繁重的特征工程工作中解救出来,这对于实际的工业应用是至关重要的。

1
2
3
4
5
6
优势
LS-PLM的优势在于在三个方面对网络规模的数据挖掘具有优势。
非线性。有了足够的划分区域,LS-PLM可以适应任何复杂的非线性函数。
可扩展性。与LR模型类似,LS-PLM可以扩展到大量样本和高维特征。
稀疏性。
工业模型,可以处理具有1000万个参数的10亿个样本的问题,这就是典型的工业数据量。

由于其能够捕获非线性模式的能力和对海量数据的可扩展性,LS-PLMs已经成为在线显示广告系统中主要的CTR预测榜样,自2012年以来为数亿用户提供服务,成为阿里巴巴在线展示广告系统中主要的点击率预测模型。

Deep & Cross Network

applies feature crossing in an automatic fashion.

以自动的方式进行特征交叉,可以处理大量的稀疏和密集的特征集,并与传统的深层网络共同学习程度有限的显性交叉特征。

1
2
3
原文表述
can handle a large set of sparse and dense features, and learns explicit cross features
of bounded degree jointly with traditional deep representations.

Attentional Factorization Machine(AFM)

AFM是FM的一个变种,传统的FM是将嵌入向量的内积均匀地加起来。AFM可以被看作是特征相互作用的加权和。

1
2
原文表述
AFM is a variant of FM,tradional FM sums the inner product of embedding vector uniformly. AFM can be seen as weighted sum of feature interactions.The weight is learned by a small MLP.

AFM弥补了FM对于不同的特征交互不能赋予不同权重的问题。

Neural Factorization Machine

NFM使用一个双交互池层来学习嵌入向量之间的特征交互,并将结果压缩成一个单一的向量,其大小与单一嵌入向量相同。MLP的输出对数和线性部分的输出对数相加,得到预测概率。

1
2
原文表述
NFM use a bi-interaction pooling layer to learn feature interaction between embedding vectors and compress the result into a singe vector which has the same size as a single embedding vector. And then fed it into a MLP.The output logit of MLP and the output logit of linear part are added to get the prediction probability.

FM的性能可能受到其线性的限制,以及仅对成对(即二阶)特征的相互作用进行建模。特别是,对于具有复杂和非线性基础结构的真实世界数据,FM可能无法表达。

NFMs:一个用于稀疏数据预测的新模型,将线性分解机的有效性与非线性神经网络的强大表示能力结合起来,用于稀疏预测分析。通过对高阶和非线性特征的相互作用的建模,增强了FMs的功能。NFM结构的关键是新提出的双交互操作。

xDeepFM

xDeepFM可以自动学习显性和隐性的高阶特征交互,这对于减少人工特征工程的工作具有重要意义。它是将一个CIN和一个DNN纳入一个端到端的框架中所产生的。

原文表述

1
Thus xDeepFM can automatically learn high-order feature interactions in both explicit and implicit fashions, which is of great significance to reducing manual feature engineering work.

xDeepFM使用压缩交互网络(CIN)来显式学习低阶和高阶特征交互,并使用MLP来隐式学习特征交互。在CIN的每一层,首先计算$x^k$和$x0$之间的外积,得到一个张量$Z{k+1}$,然后使用1DConv来学习这个张量上的特征图$H_{k+1}$。最后,对所有的特征图$H_k$应用总和池,得到一个向量。该向量用于计算CIN的贡献对数。

原文表述

1
xDeepFM use a Compressed Interaction Network (CIN) to learn both low and high order feature interaction explicitly,and use a MLP to learn feature interaction implicitly. In each layer of CIN,first compute outer products between $x^k$ and $x_0$ to get a tensor $Z_{k+1}$,then use a 1DConv to learn feature maps $H_{k+1}$ on this tensor. Finally,apply sum pooling on all the feature maps $H_k$ to get one vector.The vector is used to compute the logit that CIN contributes.

Deep Interest Network

出发点

1
在传统的深度CTR模型中,使用固定长度的表示法是捕捉用户兴趣多样性的一个瓶颈。用户的各种兴趣被压缩到一个固定长度的向量中,这限制了嵌入和MLP方法的表达能力。

深度兴趣网络(DIN),它通过考虑到候选广告的历史行为的相关性,自适应地计算用户兴趣的表示向量。

原文表述

1
Deep Interest Network (DIN), which adaptively calculates the representation vector of user interests by taking into consideration the relevance of historical behaviors given a candidate ad. 

DIN引入了一种注意力方法来学习序列(多值)特征。传统的方法通常在序列特征上使用和/均值池。DIN使用一个局部激活单元来获得候选项目和历史项目之间的激活分数。用户的兴趣由用户行为的加权和表示,用户的兴趣向量和其他嵌入向量被连接起来,并输入MLP得到预测。

原文表述

1
DIN introduce a attention method to learn from sequence(multi-valued) feature. Tradional method usually use sum/mean pooling on sequence feature. DIN use a local activation unit to get the activation score between candidate item and history items. User’s interest are represented by weighted sum of user behaviors. user’s interest vector and other embedding vectors are concatenated and fed into a MLP to get the prediction.

Deep Interest Evolution Network

出发点

1
2
1.包括DIN在内的大多数兴趣模型都将行为直接视为兴趣,而潜在的兴趣则很难通过显性行为完全反映出来。
2.用户的兴趣是不断变化的,捕捉兴趣的动态对于兴趣的表达是非常重要的。

深度兴趣进化网络(DIEN)使用兴趣提取器层,从历史行为序列中捕捉时间性兴趣。在这一层,提出了一个辅助损失来监督每一步的兴趣提取。由于用户的兴趣是多样化的,特别是在电子商务系统中,兴趣演化层被提出来捕捉与目标项目有关的兴趣演化过程。在兴趣演化层,注意力机制被新颖地嵌入到顺序结构中,并且在兴趣演化过程中加强了相对兴趣的影响。

原文表述

1
Deep Interest Evolution Network (DIEN) uses interest extractor layer to capture temporal interests from history behavior sequence. At this layer, an auxiliary loss is proposed to supervise interest extracting at each step. As user interests are diverse, especially in the e-commerce system, interest evolving layer is proposed to capture interest evolving process that is relative to the target item. At interest evolving layer, attention mechanism is embedded into the sequential structure novelly, and the effects of relative interests are strengthened during interest evolution.

关于DIEN详情可参照本人的另一篇博客

1
https://perfect-player.github.io/2022/01/09/DIEN/

AutoInt

该模型能够以明确的方式自动学习高阶特征的相互作用。方法的关键的关键是新引入的交互层,它允许每个特征与其他特征交互,并通过学习来确定相关性。

原文表述

1
The key to our method is the newly-introduced interacting layer, which allows each feature to interact with the others and to determine the relevance through learning.

AutoInt使用交互层来模拟不同特征之间的相互作用。在每个交互层中,每个特征都被允许与其他所有的特征进行交互,并且能够自动识别相关的特征,通过多头关注机制形成有意义的高阶特征。通过堆叠多个交互层,AutoInt能够对不同等级的特征交互进行建模。

原文表述

1
AutoInt use a interacting layer to model the interactions between different features. Within each interacting layer, each feature is allowed to interact with all the other features and is able to automatically identify relevant features to form meaningful higher-order features via the multi-head attention mechanism. By stacking multiple interacting layers,AutoInt is able to model different orders of feature interactions.

ONN

出发点

1
很少有工作专注于改进由嵌入层学习的特征表示

与传统的特征嵌入方法相比,操作感知嵌入方法为所有操作学习一种表征。

原文表述

1
Compared with the traditional feature embedding method which learns one representation for all operations, operation-aware embedding can learn various representations for different operations.

ONN对二阶特征交互进行建模,就像FFM一样,并尽可能地保留二阶交互信息。此外,深度神经网络被用来学习高阶特征交互。

原文表述

1
ONN models second order feature interactions like like FFM and preserves second-order interaction information as much as possible.Further more,deep neural network is used to learn higher-ordered feature interactions.

FiBiNET(Feature Importance and Bilinear feature Interaction NETwork)

提出了特征重要性和双线性特征交互网络,以动态学习特征重要性和细粒度的特征交互。一方面,FiBiNET可以通过Squeeze-Excitation网络(SENET)机制动态地学习特征的重要性;另一方面,它能够通过双线性函数有效地学习特征的相互作用。

原文表述

1
Feature Importance and Bilinear feature Interaction NETwork is proposed to dynamically learn the feature importance and fine-grained feature interactions. On the one hand, the FiBiNET can dynamically learn the importance of fea- tures via the Squeeze-Excitation network (SENET) mechanism; on the other hand, it is able to effectively learn the feature interactions via bilinear function.

目的

于动态学习特征重要性和细粒度的特征相互作用。

1
proposed to dynamically learn the feature importance and finegrained feature interactions. 

优势

1
2
3
4
1.对于CTR任务。SENET模块可以动态地学习特征的重要性。它提高了重要特征的权重,抑制了不重要特征的权重。
2.引入了三种类型的双线性交互层来学习特征的交互作用,而不是通过计算特征的交互作用。
3.在浅层模型中,将SENET机制与双线性特征交互结合起来,优于其他浅层、
4.将经典的深度神经网络(DNN)组件与浅层模型相结合,成为一个深度模型。
1
2
3
4
5
 1) For CTR task,the SENET module can learn the importance of features dynamically. It boosts the weight of the important feature and suppresses the weight of unimportant features. 
2) We introduce three types of Bilinear-Interaction layers to learn feature interaction rather
than calculating the feature interactions with Hadamard product or inner product.
3) Combining the SENET mechanism with bilinear feature interaction in our shallow model outperforms other shallow models such as FM and FFM.
4) In order to improve performance further, we combine a classical deep neural network(DNN) component with the shallow model to be a deep model. The deep FiBiNET consistently outperforms the other state-of-the-art deep models such as DeepFM and XdeepFM.

IFM

输入感知因子机(IFM)通过神经网络为不同实例中的同一特征学习一个独特的输入感知因子。

1
Input-aware Factorization Machine (IFM) learns a unique input-aware factor for the same feature in different instances via a neural network.

适用于稀疏的数据集。它的目的是通过有目的地学习更灵活、更准确的特征,来增强传统的FM。

1
It aims to enhance traditional FMs by purposefully learning more flexible and accurate representation of features for different instances with the help of a factor estimating network. 

IFM的两个主要优势

1
2
1.与现有的技术相比,它能产生更好的预测结果
2.它能更深入地了解每个特征在预测任务中的作用。
1
2
i). it produces better prediction results compared to existing techniques
ii). it provides deeper insights into the role that each feature plays in the prediction task.

DCN V2

以一种富有表现力而又简单的方式为显式交叉建模,观察到交叉网络中权重矩阵的低秩性质。

1
Observing the low-rank nature of the weight matrix in the cross network

DIFM

双输入感知因式分解机(DIFM)可以同时在比特级和矢量级对原始特征表示进行自适应的重新加权。此外,DIFM战略性地将包括多头自适应、残差网络和DNN在内的各种组件整合到一个统一的端到端模型中。

1
Dual Inputaware Factorization Machines (DIFM) can adaptively reweight the original feature representations at the bit-wise and vector-wise levels simultaneously.Furthermore, DIFMs strategically integrate various components including Multi-Head Self-Attention, Residual Networks and DNNs into a unified end-to-end model.

目的是根据不同的输入实例,借助DIFMs,自适应地学习一个给定特征的灵活表示。

1
It aims to adaptively learn flexible representations of a given feature according to different input instances with the help of the Dual-Factor Estimating Network (Dual-FEN).

主要优点是它不仅能在比特级,而且能在矢量级同时有效地学习输入感知因子(用于重新加权原始特征表示)。

1
The major advantage of DIFM is that it can effectively learn the inputaware factors (used to reweight the original feature representations) not only at the bit-wise level but also at the vectorwise level imultaneously.

AFN

自适应因子化网络(AFN)可以从数据中自适应地学习任意等级的交叉特征。AFN的核心是一个对数转换层,将特征组合中每个特征的功率转换成要学习的系数。

1
Adaptive Factorization Network (AFN) can learn arbitrary-order cross features adaptively from data. The core of AFN is a logarith- mic transformation layer to convert the power of each feature in a feature combination into the coefficient to be learned.

AFN能够从数据中自适应地学习任意顺序的特征互动。而不是在一个固定的最大顺序内对所有的交叉特征进行明确的建模。
AFN能够自动生成辨别性的交叉特征和相应特征的权重。

1
2
learns arbitrary-order feature interactions adaptively from data. Instead of explicitly modeling all the cross features within a fixed maximum order,AFN is able to generate discriminative cross features and
the weights of the corresponding features automatically.

Deep Interest Evolution Network for Click-Through Rate Prediction

前言

阿里CTR预估模型—-DIEN(深度兴趣演化网络)

这是一篇一篇阿里2019发表在AAAI上的CTR预估的论文,本文亮点主要是作者提出了兴趣提取层与兴趣演化层两个网络层。

附一个原文链接

1
https://arxiv.org/abs/1809.03672v1

背景

每点击付费(CPC) 是广告系统中最常见的计费形式之一,广告商对广告的每次点击进行收费。在CPC广告系统中,点击率(CTR)预测的效果不仅影响整个平台的最终收益,还会影响用户体验和满意度。

在大多数非搜索的电子商务场景中,用户不主动表达自己当前的意愿。因此设计能够捕捉用户动态兴趣的模型是提高CTR预测性能的关键。

研究状态

注,本文的研究状态为到2019年以前。

a.由于深度学习在特征表示上的强学习能力,目前大部分CTR模型从传统的线性或非线性模型(例如FM)转换到深度模型。

b.大多数深度模型遵循Embedding+多层感知器(MLP)的结构, 但这些模型只关注从不同的领域捕获特征之间的交互,【没有考虑到用户兴趣的表示】。

c.DIN引入了一个attention机制来激活具有意义的历史行为。但

1
2
DIN很难捕捉潜在的用户兴趣;
用户兴趣是不断发展,DIN在捕获用户序列的行为之间的依赖有所欠缺。

d.大多数基于RNN的模型都【连续且均等地处理相邻行为之间的所有依赖关系】。但并非所有用户的行为都严格取决于每个相邻的行为。 每个用户都有不同的兴趣,并且每个兴趣都有其自己的发展轨迹,例如书籍和衣服的发展过程几乎是各自独立的。 对于目标物品,这些模型只能获得一个固定的兴趣演化轨迹,可能会受到兴趣漂移的干扰。【简而言之,就是缺少Attention机制】

1
兴趣漂移:兴趣漂移对行为的影响是用户可能在一段时间内对各种书籍产生兴趣,在另一段时间内又需要衣服。

创新

a.兴趣提取器层(interest extractor layer):首先DIEN选择GRU来建模两行为之间的依赖性。其次由于隐藏状态缺乏对兴趣表示的监督,作者提出了辅助损失,即使用下一个行为来监督当前隐藏状态的学习。作者把这些有额外监督的隐藏状态称为【兴趣状态】,有助于捕获更多的语义意义用于兴趣表示,推动GRU的隐藏状态,从而有效地表示兴趣。

b.兴趣演化层(interest evolving layer):兴趣的多样性会导致兴趣偏移的现象。在相邻的访问中,用户的意图可能非常不同,用户的一个行为可能依赖于很久以前的行为。因此,作者提出建立与目标物相关的兴趣演化轨迹模型,设计了带有注意力机制更新门的GRU—-AUGRU。运用兴趣状态和目标物体去计算相关性。AUGRU增强了在兴趣演化中相关兴趣的影响,同时削弱了兴趣漂移所产生的非相关兴趣效应。通过在更新门中引入注意机制,AUGRU可以实现针对不同目标物体的特定兴趣演化过程。

主要贡献

a.提出一个新的网络结构来对兴趣演化过程进行建模。兴趣表示更具有表达性,CTR预估更精确。

b.设计了一个兴趣提取层。指出GRU对兴趣表示的针对性弱,故提出辅助损失。

c.设计了一个兴趣演化层,AUGRU增强了相关兴趣对目标物体的影响。

具体细节

DIN与DIEN的总体思路

1
在MLP的基础上,引入先验知识,加速模型训练,提高模型准确性。

image-20220110103347882image-20220110103434044

兴趣

1
2
3
4
兴趣是用来表达行为,行为则是挖掘兴趣。
对兴趣建模的任务就是从用户的历史行为中,挖掘出用户的兴趣,将兴趣
这个抽象的概念量化表达。
因此训练数据中,需要引入用户的历史点击行为。

DIN与DIEN的区别就是兴趣的建模方式不同。

DIN兴趣建模思路与缺点

image-20220110104128810

在DIN中,直接将每个历史行为等价于用户兴趣(方框处)。然后通过注意力机制,模拟处候选广告与每个历史点击之间的相关性,从而判断用户对候选广告感兴趣的程度。

缺点

1
2
3
4
5
6
对兴趣的表达,不能完全贴合实际情况。
a.直接吧行为等价成兴趣
b.很难通过已表现出来的行为,来反映出用户的潜在兴趣
c.之前的方法,忽略了去挖掘潜藏在用户行为背后的兴趣
eg:假设你当下点击了鞋子,则DIN认为你是对于鞋子感兴趣的,但是你背后的兴趣可能是多样的,例如还可能对衣服感兴趣。
DIN忽略了序列信息,容易基于用户所有购买历史行为综合推荐,而不是针对下一次购买推荐。

兴趣的实际情况

1
2
3
4
a.人的兴趣是多样的,在同一个时刻,拥有多种不同的兴趣应该用兴趣状态来描述。但是DIN只能捕捉到用户的一个兴趣。
b.兴趣是动态变换,都有属于自己的演化过程。但是DIN没有动态演化过程,例如你买完鞋子以后你可能对鞋子不感兴趣了,但是DIN还是会认为你对鞋子感兴趣。
c.兴趣的发展是有前后关联的
d.兴趣会存在兴趣漂移

DIEN对兴趣的建模思路

循环神经网络满足上述兴趣的特点

1
2
3
a.使用循环神经网络,从用户的序列行为信息中,提取出用户的兴趣状态
b.每个时刻下的兴趣状态用一个向量来表征,这个向量相当于一个黑盒,当中包含了丰富的语义信息,例如用户当前有哪些兴趣、对各个兴趣的强烈程度。
c.利用循环神经网络的串联结构,以及记忆特性,找到用户兴趣演化的规律。

步骤

1
2
a.从用户历史行为中提取出每个时刻的兴趣状态
b.利用注意力机制,找到与候选广告相关的那部分兴趣的演化过程,判断用户下一时刻对该兴趣的感兴趣程度

DIEN详解

image-20220110115254821

核心为历史行为处理部分,往右依次是目标广告,上下文特征,用户行为特征。

核心部分分为三层,从下到上为行为序列层,兴趣抽取层,兴趣进化层

兴趣抽取层

作用

1
挖缺并提取出每个时刻下,用户行为背后潜藏的兴趣状态。

采用的序列模型为GRU,具有记忆特性,可以缓解梯度消失,训练参数小于LSTM。

1
2
具体可参考:
https://zhuanlan.zhihu.com/p/32481747

结构:多输入,多输出

为更好的提取,设计了auxiliary loss

image-20220110120300856

1
2
3
4
这里设计了一个二分类模型来计算兴趣抽取的准确性,
我们将用户下一时刻真实的行为e(t+1)作为正例,
负采样得到的行为作为负例e(t+1)',
分别于抽取出的兴趣h(t)结合输入到设计的辅助网络中,得到预测结果,并通过logloss计算一个辅助的损失

原因

1
如果只采用最后的label去监督,则隐藏层所有状态都是为最后一个状态服务,则提取出的隐藏层状态显然失真。

训练方式:引入负采样训练

兴趣进化层

兴趣演化的特点

1
存在兴趣漂移,每个兴趣都有自己的演化过程

作用

1
模拟出与目标广告相关的进化机制

DIEN创新点

1
把这个注意力操作嵌入到GRU的更新门里面去,形成了一个AUGRU的结构,用这个层来更有针对性的模拟与目标广告相关的兴趣进化路径

得到过程

AIGRU

image-20220110122005893

image-20220110122133352

直接拿$a_t$乘上了兴趣抽取层的隐藏兴趣状态,但会使不相干的兴趣会影响到兴趣演化层的学习

AGRU

image-20220110122118801

拿$a_t$替换掉了更新门。

若某个时刻t的兴趣$h_t$与当前候选广告一点关系没有,即$a_t$为0,这个时候的隐藏状态会直接使用上一时刻的。

通过这种机制保障只关注和当前候选广告相关的兴趣演化过程。

问题

1
在替换时用标量替换向量,忽视了不同维度上值的重要性
AUGRU

image-20220110122639019

克服了AGRU忽略维度的问题。

总结

本文提出了一种新的深层网络结构,即深层兴趣演化网络(DIEN),来模拟兴趣的演化过程。在在线广告系统中,DIEN极大地提高了CTR预测的性能。具体地说,作者设计了

  • 兴趣提取层来捕获兴趣序列,利用辅助损失来提供对兴趣状态的更多监督。
  • 兴趣演化层,使用带有注意力更新门(AUGRU)的GRU来模拟与目标物品相关的兴趣演化过程。在AUGRU的帮助下,DIEN克服了兴趣漂移的干扰。兴趣演化建模有助于有效捕获兴趣,进一步提高CTR预测的性能。

鸣谢

B站,老弓的学习日记

存疑

z=x+1;的中间代码生成

移植问题(已解决)

image-20220419121711994

虚属性?

中间代码生成,修改

image-20220514151221654

习题8.4 是否存在和这些规则一致的求值过程

9.1

9 10

12.2

13.3

14.6

15.4 15.5

重点

消除左递归

递归下降语法分析器

非递归下降语法分析器

句柄

判断是否为LL文法

LR文法的四种判断

1
关系:LR(0)<SLR(1)<LALR(1)<LR(1)

1.判断LR(0)文法:
看项目中是否有归约-归约和移进-归约冲突。
如果无冲突则是LR(0)文法(如果是LR(0)文法则四种都是);如果有冲突则不是LR(0)文法。(就要向下判断)

2.判断SLR(1)文法:
a:DFA中存在冲突项目(归约-归约,归约-移进)
b:{a1,a2,…,an},FOLLOW(B1),FOLLOW(B2)两两互不相交,(交集=空集)时是SLR(1)项目。
【也就是说,同时满足两个条件才是SLR(1)文法】

若不是再向下判断。

3.判断LR(1)文法:
构造带向前搜索符的DFA,无归约-归约冲突则是LR(1)文法。

【此处意思是如果有向前搜索符还有冲突的话就不是LR(1)文法,就要再向下判断】

4.判断LALR(1)文法:
合并同心集后无(归约-归约)冲突(在之前的基础上)
(核相同,向前搜索符不同)

(B->a,a
B->a,a|b
同心集)
LR(0)项目集规范族的构造和分析的构造

1
https://blog.csdn.net/m0_37154839/article/details/80316089

设计SDD

改写SDT

四元式序列

1
https://blog.csdn.net/abc123lzf/article/details/103753507

中间代码生成

image-20220518170348404

image-20220518170539086

image-20220518170614471

赋值语句的翻译

1
2
3
newtemp( ):生成一个新的临时变量t,返回t的地址
gen(code):生成三地址指令code
lookup(name):查询符号表返回name 对应的记录

数组引用的翻译

1
2
3
4
L的综合属性
L.type:L生成的数组元素的类型
L.offset:指示一个临时变量,该临时变量用于累加公式中的ij × wj项,从而计算数组元素的偏移量
L.array:数组名在符号表的入口地址

控制语句的翻译

1
2
3
4
继承属性
B.true:是一个地址,该地址用来存放当B为真时控制流转向的指令的标号
B.false:是一个地址,该地址用来存放当B为假时控制流转向的指令的标号
S.next:是一个地址,该地址用来存放紧跟在S代码之后执行的指令(S的后继指令)的标号

回填

非终结符B的综合属性

1
2
B.truelist:指向一个包含跳转指令的列表,这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
B.falselist:指向一个包含跳转指令的列表,这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

函数

1
2
3
4
5
6
makelist( i )
创建一个只包含i的列表,i是跳转指令的标号,函数返回指向新创建的列表的指针
merge( p1, p2 )
将 p1 和 p2 指向的列表进行合并,返回指向合并后的列表的指针
backpatch( p, i )
将 i 作为目标标号插入到 p所指列表中的各指令中
1
nextquad:即将生成的下一条指令的标号

image-20220517011523873

什么是编译

编译:将高级语言翻译成汇编语言机器语言的过程。

image-20220104110715843

预处理器:把存储在不同文件中的源程序聚合在一起;把被称为宏的缩写语句转换为原始语句。

可重定位:在内存中存放的起始位置L不是固定的

加载器:修改可重定位地址;将修改后的指令和数据放到内存中适当的位置。

链接器:将多个可重定位的机器代码文件连接到一起;解决外部内存地址问题

编译系统的结构

image-20220104113047587

词法分析概述

词法分析的主要任务:

1
2
从左向右逐行扫描源程序的字符,识别出各个单词,确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元(token)形式。
token:<种别码,属性值>

image-20220105104115216

语法分析概述

语法分析器从词法分析器输出的token序列中识别出各类短语,并构造语法分析树。

语义分析概述

主要任务:

任务一:收集标识符的属性信息

1
2
3
4
5
6
7

种属:简单变量、复合变量(数组,记录)、过程
类型:整型、实型、字符型、布尔型、指针型
存储类型,长度

作用域
参数和返回值信息

符号表:用来存放标识符的属性信息的数据结构

image-20220106095418057

任务二:语义检查

1
2
3
4
变量或过程未经声明就使用;
变量或过程名重复声明;
运算分量类型不匹配;
操作符与操作数之间的类型不匹配

中间代码生成及编译器后端

常用的中间表示形式:

三地址码;语法结构树/语法树

三地址码

三地址码由类似于汇编语言的指令序列组成,每个指令最多有三个操作数。

image-20220106095933969

三地址指令的表示

1
2
3
四元式(op,arg1,arg2,result)
三元式(op,arg1,arg2)
间接三元式

目标代码生成以源程序的中间表示形式作为输入,并把它映射到目标语言;目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器。

代码优化:为改进代码,所进行的等价程序变换,使其运行得更快一些,占用空间更小一些。

编译程序的生成

编译器的T形图

image-20220419112048151

自展

image-20220419112803975

移植

image-20220419112828085

语言及其文法

基本概念

字母表

1
一个有穷符号集合。

字母表运算

1
2
3
4
乘积
n次幂
正闭包(正数次幂的并集)
克林闭包(正闭包的基础上加个空串)

串:字母表中符号的一个有穷序列

串的运算

1
2
连接,空串是连接运算的单位元
串的幂运算

文法的定义

文法

$G=(V_T,V_N,P,S)$

$V_T$:终结符集合

1
终结符是文法所定义的语言的基本符号,有事也称为token

$V_N$:非终结符集合

1
非终结符是用来表示语法成分的符号,有时也称为"语法变量"

$V_T$与$V_N$不相交,二者相并统称为文法符号集。

P:产生式集合

1
描述了将终结符和非终结符组合成串的方法

S:开始符号

1
开始符号表示的是该文法中最大的语法成分

image-20220107105320903

符号约定

终结符

image-20220107110153976

非终结符

image-20220107110227112

image-20220107110401057

语言的定义

符号串$a0$经过n步推导出$a_n$,可简记为$a_0\Longrightarrow {}^{n}a_n $

image-20220108100026833

句子是不包含非终结符的句型。

文法的分类

Chomsky文法分类体系

0型文法

$\alpha \longrightarrow \beta $

无限制文法,其中$\alpha$中至少包含一个非终结符。

由0型文法G生成的语言称为 0型语言

1型文法

$\alpha \longrightarrow \beta $

上下文有关文法,CSG

产生式的一般形式:

2型文法

$\alpha \longrightarrow \beta $

上下文无关文法,CFG

其中$\alpha\in V_N$

产生式的一般形式:

3型文法

$\alpha \longrightarrow \beta $

正则文法,RG

右线性文法:$A\longrightarrow wB或A\longrightarrow w$

左线性文法:$A\longrightarrow Bw或A\longrightarrow w$

image-20220429171644864

CFG的分析树

给定一个句型,其分析树中的每一棵子树的边缘称为该句型的一个短语。

直接短语:高度为2的子树的边缘。

1
2
直接短语一定是某产生式的右部
但产生式的右部不一定是给定句型的直接短语

二义性文法

1
如果一个文法可以为某个句子生成多颗分析树,则称这个文法是二义性的。

image-20220109105001704

词法分析

正则表达式

image-20220109105354813

正则定义

image-20220111100400281

有穷自动机

image-20220111101353306

最长子串匹配原则:当输入串的多个前缀与一个或多个模式匹配时,总是选择最长的前缀进行匹配

有穷自动机的分类

DFA确定的有穷自动机

image-20220112104246612

NFA非确定的有穷自动机

image-20220112104402251

正则文法与正则表达式与有穷自动机等价

image-20220112104637911

带有空边的NFA与不带空边的NFA有等价性

从正则表达式到有穷自动机

先构造NFA,再从NFA到DFA。

根据RE构造NFA

image-20220501150009650

假设正则表达式r1和r2对应的NFA分别为N(r1)和N(r2)

image-20220501150031625

从NFA到DFA的转换

image-20220114100302890

image-20220114100719876

识别单词的DFA

词法分析阶段可检测错误的类型:

1
2
单词拼写错误
非法字符

错误恢复策略

1
2
最简单的错误恢复策略:恐慌模式
从剩余的输入中不断删除字符,直到词法分析器能够在剩余的开头发现一个正确的字符为止。

语法分析

自顶向下分析概述

从分析树的顶部向底部方向构造分析树。

1
最左推导:总是选择每个句型的最左非终结符进行替换。
1
最右推导:总是选择每个句型的最右非终结符进行替换。

在自底向上的分析中,总是采用最左规约的方式,因此把最左规约称为规范规约,而最右推导相应的称为规范推导。

自顶向下选择最左推导。

自顶向下分析存在的问题

同一非终结符的多个候选式存在共同前缀,将导致回溯现象

image-20220512192055179

左递归文法会使递归下降分析器陷入无限循环

image-20220512192124252

消除直接左递归

image-20220512192544030

消除直接左递归的一般形式

image-20220512192836269

消除间接左递归

image-20220512192935922

提取左公因子

image-20220512193513607

image-20220512193523610

预测分析

需要回溯的分析器叫不确定分析器。

1
2
预测分析:递归下降分析技术的一个特例,通过在输入中向前看固定个数符号来选择正确的A-产生式。
预测分析不需要回溯,是一种确定的自顶向下分析方法。

可以对某些文法构造出向前看k个输入符号的预测分析器,该类文法有时也称为LL(k) 文法类

预测分析法

LL(1)文法

S_文法

1
2
3
每个产生式的右部都以终结符开始
同一非终结符的各个候选式的首终结符都不同
S_文法不含ε产生式

什么时候使用ε产生式

1
如果当前某非终结符A与当前输入符a不匹配时,若存在A→ε,可以通过检查a是否可以出现在 A的后面,来决定是否使用产生式 A→ε(若文法中无 A→ε ,则应报错)

后继符号集

1
2
3
可能在某个句型中紧跟在A后边的终结符a的集合,记为FOLLOW(A)
FOLLOW(A)={a| S ->* αAaβ, a∈VT,α,β∈(VT∪VN)*}
如果 A是某个句型的的最右符号,则将结束符“$”添加到FOLLOW(A)中

产生式的可选集

1
2
3
产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为SELECT( A→β )
SELECT( A→aβ ) = { a }
SELECT( A→ε )=FOLLOW( A )

image-20220512212721662

q_文法

1
2
3
每个产生式的右部或为ε ,或以终结符开始
具有相同左部的产生式有不相交的可选集
q_文法不含右部以非终结符打头的产生式

串首终结符集

1
给定一个文法符号串α, α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。如果α * ε,那么ε也在FIRST(α)中

LL(1)文法

1
2
3
4
5
当且仅当G的任意两个具有相同左部的产生式A → α | β 满足下面的条件:
不存在终结符a使得α 和β都能够推导出以a开头的串
α 和β至多有一个能推导出ε
如果 β ->* ε,则FIRST (α)∩FOLLOW(A) =Φ;
如果 α ->* ε,则FIRST (β)∩FOLLOW(A) =Φ;

即同一非终结符的各个产生式的可选集互不相交

第一个L表示从左向右扫描输入,第二个L表示最左推导

follow(A)计算方法

image-20220512220412044

预测分析表

image-20220512220850395

预测分析

1
2
递归的方式:基于预测分析表对递归下降分析法进行扩展
非递归的方式:显式地维护一个栈结构来模拟最左推导过程

递归的预测分析法

非递归的预测分析法

非递归的预测分析显式地维护一个栈结构,而不是通过递归调用的方式隐式地维护栈。这样的语法分析器可以模拟最左推导过程

image-20220512221720701

image-20220512221741289

预测分析步骤

1
2
3
4
5
6
1.构造文法
2.改造文法:消除二义性、消除左递归、消除回溯
3.求每个变量的FIRST集和FOLLOW集,从而求得每个候选式的SELECT集
4.检查是不是 LL(1) 文法。若是,构造预测分析表
5.对于递归的预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动
的预测分析算法

二义性判定

1
对于任一个上下文无关文法,不存在一个算法判断其是否为二义性,但能给出一个充分条件,满足则无二义性,不满足也未必有二义性

预测分析中的错误检测

两种情况下可以检测到错误

1
2
栈顶的终结符和当前输入符号不匹配
栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

错误恢复

1
恐慌模式:忽略输入中的一些符号,直到输入中出现由设计者选定的同步词法单元(synchronizing token)集合中的某个词法单元;如果终结符在栈顶而不能匹配,一个简单的办法就是弹出此终结符

自底向上的分析

自底向上的语法分析采用最左归约方式(反向构造句子的最右推导)

移入-归约分析

工作过程

image-20220513095056700

四种动作

1
2
3
4
移入:将下一个输入符号移到栈的顶端
归约:被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端,并决定用哪个非终结符来替换这个串
接收:宣布语法分析过程成功完成
报错:发现一个语法错误,并调用错误恢复子例程

存在问题

1
2
归约-归约冲突
移入-归约冲突

归约-归约冲突

造成错误的原因:错误地识别了句柄

句柄:句型的最左直接短语

image-20220513100212940

移入-归约冲突

image-20220513100150507

LR分析法

是最大的、可以构造出相应移入-归约语法分析器的文法类
L: 对输入进行从左到右的扫描
R: 反向构造出一个最右推导序列

LR(k)分析
需要向前查看k个输入符号的LR分析

image-20220513102223085

image-20220513102611274

看PPT例题分析

LR(0) 分析

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目(简称为项目)

image-20220513103304315

产生式A→ε 只生成一个项目A→ ·

增广文法

1
如果G 是一个以S为开始符号的文法,则G的增广文法 G' 就是在G中加上新开始符号S' 和产生式S' → S而得到的文法

image-20220513103407672

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边,从而使得分析器只有一个接受状态

image-20220513103852131

初始项目:S’→·S

接收项目:S’→S·

归约项目:·在末尾的项目

后继项目:同属于一个产生式的项目,但圆点的位置只相差一个符号, 则称后者是前者的后继项目

A→α· Xβ的后继项目是A→αX·β

可以把等价的项目组成一个项目集( I ) ,称为项目集闭包(Closure of Item Sets),每个项目集闭包对应着自动机的一个状态

eg:

image-20220513104546195

image-20220513104843423

image-20220513104852180

LR(0)分析过程的冲突

移进归约冲突

image-20220513105245484

image-20220513105343336

在状态2时,当遇到*号时,不清楚应该移入还是归约。

归约归约冲突

image-20220513105500066

状态二有两个归约和一个移入,移进/归约冲突和归约/归约冲突混合。

如果LR(0)分析表中没有语法分析动作冲突,那么给定的文法就称为LR(0)文法

不是所有CFG(上下文无关文法)都能用LR(0)方法进行分析,也就是说,CFG不总是LR(0)文法。

SLR 分析

LR(0)解决不了冲突的原因

1
2
句柄都是相对一个句型而言的,因此应该将句柄的识别放在句型这样一个上下文环境中考虑
LR(0)考虑了A的上文(规范句型的前缀),但未考虑A的下文,因此消解冲突能力有限

image-20220513135613449

SLR冲突

image-20220513135724655

当状态2遇到=时,会有移入归约冲突。

存在问题

1
SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A),但b∈FOLLOW(A)只是归约α的一个必要条件,而非充分条件

LR(1)分析

在特定位置,A的后继符集合是FOLLOW(A)的子集,而SLR分析法则将其全部考虑了进去。

将一般形式为 [A→α·β, a]的项称为 LR(1) 项,其中A→αβ 是一个产生式,a 是一个终结符(这里将$视为一个特殊的终结符)它表示在当前状态下,A后面必须紧跟的终结符,称为该项的展望符(lookahead)

1
2
3
4
LR(1) 中的1指的是项的第二个分量的长度
在形如[A→α·β, a]且β ≠ ε的项中,展望符a没有任何作用
但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α 进行归约
这样的a的集合总是FOLLOW(A)的子集,而且它通常是一个真子集

image-20220513143948062

image-20220513144511943

如果除展望符外,两个LR(1)项目集是相同的,则称这两个LR(1)项目集是同心的

LR(1)分析实际上是根据后继符集合的不同,将原始的LR(0)状态分裂成不同的LR(1)状态

LALR分析

1
2
3
寻找具有相同核心的LR  (1) 项集,并将这些项集合并为一个项集。 所谓项集的核心就是其第一分量的集合
然后根据合并后得到的项集族构造语法分析表
如果分析表中没有语法分析动作冲突,给定的文法就称为LALR (1) 文法,就可以根据该分析表进行语法分析

合并同心项集时产生归约-归约冲突的例子

image-20220513145829960

合并同心项集不会产生移进-归约冲突

合并同心项集后,虽然不产生冲突,但可能会推迟错误的发现

LALR分析法可能会作多余的归约动作,但绝不会作错误的移进操作

LALR(1)的特点

1
2
3
4
形式上与LR(1)相同
大小上与LR(0)/SLR相当
分析能力介于SLR和LR(1)二者之间:LR(0)< SLR<LALR(1)<LR(1)
合并后的展望符集合仍为FOLLOW集的子集

二义性文法的LR分析

每个二义性文法都不是LR的
某些类型的二义性文法在语言的描述和实现中很有用

用优先级和结合性解决冲突

应该保守地使用二义性文法,并且必须在严格控制之下使用,因为稍有不慎就会导致语法分析器所识别的语言出现偏差

LR分析中的错误处理

语法错误的检测

1
当LR分析器在查询语法分析动作表并发现一个报错条目时,就检测到了一个语法错误

错误恢复策略

1
2
恐慌模式错误恢复
短语层次错误恢复

恐慌错误恢复

1
2
3
4
从栈顶向下扫描,直到发现某个状态si,它有一个对应于某个非终结符A的GOTO目标,可以认为从这个A推导出的串中包含错误
然后丢弃0个或多个输入符号,直到发现一个可能合法地紧跟在A之后的符号a为止
之后将si+1 = GOTO(si , A)压入栈中,继续进行正常的语法分析
实践中可能会选择多个这样的非终结符A。通常这些非终结符代表了主要的程序段,比如表达式、语句或块

短语层次错误恢复

1
2
检查LR分析表中的每一个报错条目,并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误
然后构造出适当的恢复过程

image-20220513151319857

语法制导翻译

语法制导翻译使用CFG来引导对语言的翻译,是一种面向文法的翻译技术

基本思想

1
2
3
如何表示语义信息:为CFG中的文法符号设置语义属性,用来表示语法成分对应的语义信息
如何计算语义属性:文法符号的语义属性值是用与文法符号所在产生式(语法规则)相关联的语义规则来计算的
对于给定的输入串x ,构建x的语法分析树,并利用与产生式(语法规则)相关联的语义规则来计算分析树中各结点对应的语义属性值

语法制导定义(Syntax-Directed Definitions, SDD)

1
2
3
4
SDD是对CFG的推广
将每个文法符号和一个语义属性集合相关联
将每个产生式和一组语义规则相关联,这些规则用于计算该产生式中各文法符号的属性值
如果X是一个文法符号,a是X的一个属性,则用X.a表示属性a在某个标号为X的分析树结点上的值

语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT )

1
SDT是在产生式右部嵌入了程序片段的CFG,这些程序片段称为语义动作。一个语义动作在产生式中的位置决定了这个动作的执行时间

语法制导定义SDD

概述

语法制导定义SDD是对CFG的推广

1
2
将每个文法符号和一个语义属性集合相关联
将每个产生式和一组语义规则相关联,用来计算该产生式中各文法符号的属性值

文法符号的属性

1
2
综合属性 (synthesized attribute)
继承属性 (inherited attribute)

综合属性

1
2
在分析树结点 N上的非终结符A的综合属性只能通过 N的子结点或 N本身的属性值来定义
终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值,因此在SDD中没有计算终结符属性值的语义规则

继承属性

1
2
在分析树结点 N上的非终结符A的继承属性只能通过 N的父结点、N的兄弟结点或 N本身的属性值来定义
终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值

属性文法

1
2
一个没有副作用的SDD有时也称为属性文法
属性文法的规则仅仅通过其它属性值和常量来定义一个属性值

SDD的求值顺序

语义规则建立了属性之间的依赖关系,在对语法分析树节点的一个属性求值之前,必须首先求出这个属性值所依赖的所有属性值

依赖图

1
2
3
依赖图是一个描述了分析树中结点属性间依赖关系的有向图
分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
如果属性X.a的值依赖于属性Y.b的值,则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

eg:image-20220513155754626

属性值计算顺序

1
这样的排序将一个有向图变成了一个线性排序,这个排序称为这个图的拓扑排序
1
2
3
对于只具有综合属性的SDD ,可以按照任何自底向上的顺序计算它们的值
对于同时具有继承属性和综合属性的SDD,不能保证存在一个顺序来对各个节点上的属性进行求值
如果图中没有环,那么至少存在一个拓扑排序

S-属性定义与L-属性定义

仅仅使用综合属性的SDD称为S属性的SDD,或S-属性定义、S-SDD

如果一个SDD是S属性的,可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值

L-属性定义(也称为L属性的SDD或L-SDD)的直观含义:在一个产生式所关联的各属性之间,依赖图的边可以从左到右,但不能从右到左

正式定义

1
2
3
4
一个SDD是L-属性定义,当且仅当它的每个属性要么是一个综合属性,要么是满足如下条件的继承属性:假设存在一个产生式A→X1X2…Xn,其右部符号Xi (1<= i <= n)的继承属性仅依赖于下列属性:
A的继承属性
产生式中Xi左边的符号 X1, X2, … , Xi-1 的属性
Xi本身的属性,但Xi 的全部属性不能在依赖图中形成环路

虚属性:就是一个动作,不干其他事情。

语法制导翻译方案SDT

语法制导翻译方案(SDT )是在产生式右部中嵌入了程序片段(称为语义动作)的CFG

SDD定义了各属性的计算方法(计算规则),SDT进一步明确了各属性的计算时机(计算顺序)

这两种情况下,SDT可在语法分析过程中实现

1
2
基本文法可以使用LR分析技术,且SDD是S属性的
基本文法可以使用LL分析技术,且SDD是L属性的

S-SDD转换为SDT

将每个语义动作都放在产生式的最后

S-属性定义的SDT 实现

1
2
如果一个S-SDD的基本文法可以使用LR分析技术,那么它的SDT可以在LR语法分析过程中实现
当归约发生时执行相应的语义动作

语法分析器的扩展

1
2
为每个栈记录增加属性值字段,存放文法符号的综合属性值
在每次归约时调用计算综合属性值的语义子程序

image-20220513164603555

image-20220513164616906

image-20220513164754145

将L-SDD转换为SDT

1
2
将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

如果一个L-SDD的基本文法可以使用LL分析技术,那么它的SDT可以在LL或LR语法分析过程中实现

1
2
3
在非递归的预测分析过程中进行语义翻译
在递归的预测分析过程中进行语义翻译
在LR分析过程中进行语义翻译

L-属性定义的自顶向下翻译

在非递归的预测分析过程中进行翻译

扩展语法分析栈

image-20220513205659076

看例题

分析栈中的每一个记录都对应着一段执行代码

1
2
综合记录出栈时,要将综合属性值复制给后面特定的语义动作
变量展开时(即变量本身的记录出栈时),如果其含有继承属性,则要将继承属性值复制给后面特定的语义动作

在递归的预测分析过程中进行翻译

为每个非终结符A构造一个函数,A的每个继承属性对应该函数的一个形参,函数的返回值是A的综合属性值

对出现在A产生式右部中的每个文法符号的每个属性都设置一个局部变量

例题

算法

1
2
为每个非终结符A构造一个函数,A的每个继承属性对应该函数的一个形参,函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量
非终结符A的代码根据当前的输入决定使用哪个产生式

L-属性定义的自底向上翻译

给定一个以LL文法为基础的L-SDD,可以修改这个文法,并在LR语法分析过程中计算这个新文法之上的SDD

1
2
3
4
5
6
给定一个以LL文法为基础的L-属性定义,可以修改这个文法,并在LR语法分析过程中计算这个新文法之上的SDD
首先构造SDT,在各个非终结符之前放置语义动作来计算它的继承属性, 并在产生式后端放置语义动作计算综合属性
对每个内嵌的语义动作,向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记,并且对于任意一个标记M都有一个产生式M→ε
如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a,对a进行修改得到a' ,并且将a'关联到M→ε 上。动作a'
(a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
(b) 按照a中的方法计算各个属性,但是将计算得到的这些属性作为M的综合属性

中间代码生成

声明语句的翻译

主要任务

1
收集标识符的类型等属性信息,并为每一个名字分配一个相对地址

名字的类型和相对地址信息保存在相应的符号表记录中

类型表达式

基本类型是类型表达式

1
2
3
4
5
6
integer
real
char
boolean
type_error (出错类型)
void (无类型)

可以为类型表达式命名,类型名也是类型表达式

将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式

数组构造符array

若T是类型表达式,则array ( I, T )是类型表达式( I是一个整数)

image-20220514094900862

指针构造符pointer

若T 是类型表达式,则 pointer ( T ) 是类型表达式,它表示一个指针类型

笛卡尔乘积构造符X

若T1 和T2是类型表达式,则笛卡尔乘积T1 X T2 是类型表达式

函数构造符→

若T1、T2、…、Tn 和R是类型表达式,则T1T2 …Tn→ R是类型表达式

记录构造符record

若有标识符N1 、N2 、…、Nn 与类型表达式T1 、T2 、…、Tn , 则 record ( ( N1 X T1 ) X ( N2 X T2 )X …X ( Nn X Tn )) 是一个类型表达式

eg:image-20220514095400390

局部变量的存储分配

对于声明语句,语义分析的主要任务就是收集标识符的类型等属性信息,并为每一个名字分配一个相对地址

1
2
从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)
在编译时刻,可以使用类型的宽度为每一个名字分配一个相对地址

名字的类型和相对地址信息保存在相应的符号表记录中

赋值语句的翻译

简单赋值语句的翻译

newtemp( ):生成一个新的临时变量t,返回t的地址

gen(code):生成三地址指令code

lookup(name):查询符号表返回name 对应的记录

增量翻译

1
在增量方法中,gen( )不仅要构造出一个新的三地址指令,还要将它添加到至今为止已生成的指令序列之后

ppt例子

数组引用的翻译

将数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址,也就是数组元素的寻址

image-20220514114112824

image-20220514142140992

image-20220514142202241

符号表的组织——数组

image-20220514142237490

控制语句的翻译

控制流语句

继承属性

1
2
3
B.true:是一个地址,该地址用来存放当B为真时控制流转向的指令的标号
B.false:是一个地址,该地址用来存放当B为假时控制流转向的指令的标号
S.next:是一个地址,该地址用来存放紧跟在S代码之后执行的指令(S的后继指令)的标号

image-20220514143929654

if-then-else

image-20220514144057301

if-then

image-20220514144152954

while-do

image-20220514144250284

控制流语句SDT编写要点

1
2
3
4
5
分析每一个非终结符之前
先计算继承属性
再观察代码结构图中该非终结符对应的方框顶部是否有导入箭头。如果有,调用label( )函数
上一个代码框执行完不顺序执行下一个代码框时,生成一条显式跳转指令
有自下而上的箭头时,设置begin属性。且定义后直接调用label( )函数绑定地址

布尔表达式的翻译

在跳转代码中,逻辑运算符&&、|| 和 ! 被翻译成跳转指令。运算符本身不出现在代码中,布尔表达式的值是通过代码序列中的位置来表示的

image-20220514144701666

布尔表达式的SDT

image-20220514144801933

image-20220514145311289

image-20220514145338517

SDT的通用实现方法

任何SDT都可以通过下面的方法实现

1
2
首先建立一棵语法分析树
然后按照从左到右的深度优先顺序来执行这些动作

例题

存疑,修改

回填

布尔表达式回填

基本思想

1
生成一个跳转指令时,暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到 能够确定正确的目标标号时,才去填充这些指令的目标标号

非终结符B的综合属性

1
2
B.truelist:指向一个包含跳转指令的列表,这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
B.falselist:指向一个包含跳转指令的列表,这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

函数

1
2
3
4
5
6
makelist( i )
创建一个只包含i的列表,i是跳转指令的标号,函数返回指向新创建的列表的指针
merge( p1, p2 )
将 p1 和 p2 指向的列表进行合并,返回指向合并后的列表的指针
backpatch( p, i )
将 i 作为目标标号插入到 p所指列表中的各指令中

例题

控制流语句回填

综合属性

1
S.next1ist:指向一个包含跳转指令的列表,这些指令最终获得的目标标号就是按照运行顺序紧跟在S代码之后的指令的标号

例题

回填技术SDT编写要点

1
2
3
4
5
文法改造
在list箭头指向的位置设置标记非终结符M
在产生式末尾的语义动作中
计算综合属性
调用backpatch ( )函数回填各个list

switch语句的翻译

image-20220514162527513

image-20220514162534065

image-20220514162733153

过程调用语句的翻译

需要一个队列q存放E1.addr 、E2.addr、…、 En.addr,以生成

image-20220514163207424

例子

运行存储分配

存储组织

一个目标程序运行所需的存储空间主要包括

image-20220514163839643

存储分配策略

1
2
3
4
5
对于那些在编译时刻就可以确定大小的数据对象,可以在编译时刻就为它们分配存储空间,这样的分配策略称为静态存储分配
反之,如果不能在编译时完全确定数据对象的大小,就要采用动态存储分配的策略。即在编译时仅产生各种必要的信息,而在运行时刻,再动态地分配数据对象的存储空间
栈式存储分配
堆式存储分配
静态和动态分别对应编译时刻和运行时刻

image-20220514194257711

活动记录

1
2
3
使用过程(或函数、方法)作为用户自定义动作的单元的语言,其编译器通常以过程为单位分配存储空间
过程体的每次执行称为该过程的一个活动(activation)
过程每执行一次,就为它分配一块连续存储区,用来管理过程一次执行所需的信息,这块连续存储区称为活动记录( activation record )

活动记录的一般形式

image-20220514194518053

静态存储分配

1
2
3
4
在静态存储分配中,编译器为每个过程确定其活动记录在目标程序中的位置
这样,过程中每个名字的存储位置就确定了
因此,这些名字的存储地址可以被编译到目标代码中
过程每次执行时,它的名字都绑定到同样的存储单元

适合静态存储分配的语言必须满足以下条件

1
2
3
数组上下界必须是常数
不允许过程的递归调用
不允许用户动态建立数据实体

满足这些条件的语言有BASIC和FORTRAN等

常用的静态存储分配方法:顺序分配法、层次分配法

顺序分配法

按照过程出现的先后顺序逐段分配存储空间
各过程的活动记录占用互不相交的存储空间

image-20220514195326335

1
2
优点:处理上简单
缺点:对内存空间的使用不够经济合理

层次分配法

通过对过程间的调用关系进行分析,凡属无相互调用关系的并列过程,尽量使其局部数据共享存储空间

image-20220514195613542

层次分配算法

image-20220514195658467

栈式存储分配

1
2
3
有些语言使用过程、函数或方法作为用户自定义动作的单元,几乎所有针对这些语言的编译器都把它们的(至少一部分的)运行时刻存储以栈的形式进行管理,称为栈式存储分配
当一个过程被调用时,该过程的活动记录被压入栈;当过程结束时,该活动记录被弹出栈
这种安排不仅允许活跃时段不交叠的多个过程调用之间共享空间,而且允许以如下方式为一个过程编译代码:它的非局部变量的相对地址总是固定的,和过程调用序列无关

活动树

1
2
3
用来描述程序运行期间控制进入和离开各个活动的情况的树称为活动树
树中的每个结点对应于一个活动。根结点是启动程序执行的main过程的活动
在表示过程p的某个活动的结点上,其子结点对应于被p的这次活动调用的各个过程的活动。按照这些活动被调用的顺序,自左向右地显示它们。一个子结点必须在其右兄弟结点的活动开始之前结束
1
2
3
4
每个活跃的活动都有一个位于控制栈中的活动记录
活动树的根的活动记录位于栈底
程序控制所在的活动的记录位于栈顶
栈中全部活动记录的序列对应于在活动树中到达当前控制所在的活动结点的路径

设计活动记录的一些原则

1
2
3
4
在调用者和被调用者之间传递的值一般被放在被调用者的活动记录的开始位置,这样它们可以尽可能地靠近调用者的活动记录
固定长度的项被放置在中间位置:控制连、访问链、机器状态字
在早期不知道大小的项被放置在活动记录的尾部
栈顶指针寄存器top_sp指向活动记录中局部数据开始的位置,以该位置作为基地址

调用序列和返回序列

1
2
3
4
5
6
过程调用和过程返回都需要执行一些代码来管理活动记录栈,保存或恢复机器状态等
调用序列
实现过程调用的代码段。为一个活动记录在栈中分配空间,并在此记录的字段中填写信息
返回序列
恢复机器状态,使得调用过程能够在调用结束之后继续执行
一个调用代码序列中的代码通常被分割到调用过程(调用者)和被调用过程(被调用者)中。返回序列也是如此

image-20220514203627726

image-20220514203641791

调用者和被调用者之间的任务划分

image-20220514203739336

变长数据的存储分配

1
2
在现代程序设计语言中,在编译时刻不能确定大小的对象将被分配在堆区。但是,如果它们是过程的局部对象,也可以将它们分配在运行时刻栈中。尽量将对象放置在栈区的原因:可以避免对它们的空间进行垃圾回收,也就减少了相应的开销
只有一个数据对象局部于某个过程,且当此过程结束时它变得不可访问,才可以使用栈为这个对象分配空间

非局部数据的访问

一个过程除了可以使用过程自身声明的局部数据以外,还可以使用过程外声明的非局部数据

1
2
全局数据
外围过程定义的数据

如何访问非局部数据

1
2
访问链(静态链)
display表(嵌套层次显示表)

访问链

1
2
3
静态作用域规则:只要过程b的声明嵌套在过程a的声明中,过程b就可以访问过程a中声明的对象
可以在相互嵌套的过程的活动记录之间建立一种称为访问链(Access link)的指针,使得内嵌的过程可以访问外层过程中声明的对象
如果过程b在源代码中直接嵌套在过程a中(b的嵌套深度比a的嵌套深度多1),那么b的任何活动中的访问链都指向最近的a的活动

嵌套深度

image-20220514205925465

例子

访问链的建立

假设嵌套深度为nx的过程x调用嵌套深度为ny的过程y (x→y)

nx < ny的情况(外层调用内层)

1
2
y一定是直接在x中定义的 (例如:s→q,  q→p) ,因此,ny=nx +1
在调用代码序列中增加一个步骤:在y的访问链中放置一个指向x的活动记录的指针

nx = ny的情况(本层调用本层 )

1
2
例如:递归调用 (q→q )
被调用者的活动记录的访问链与调用者的活动记录的访问链是相同的,可以直接复制

nx > ny的情况(内层调用外层,如: p→e )

1
2
调用者x必定嵌套在某个过程z中,而z中直接定义了被调用者y
从x的活动记录开始,沿着访问链经过nx - ny + 1步就可以找到离栈顶最近的z的活动记录。 y的访问链必须指向z的这个活动记录

嵌套深度是在编译阶段通过静态分析就能确定的

display表

慕课没有

看例题,注意嵌套深度与树无关,在编译阶段就决定。

参数传递

形式参数(formal parameter):在过程定义中使用的参数
实际参数(actual parameter):在调用过程时使用的参数

形参和实参相关联的几种方法

1
2
3
4
传值(Call- by-Value)
传地址(Call- by-Reference)
传值结果(Call- by-Value-Result)
传名(Call- by-Name)

传值

1
2
3
4
把实参的值传递给相应的形参
实现方法
调用过程把实参的值计算出来,并传递到被调用过程相应的形式单元中
被调用过程中,像引用局部数据一样引用形式参数,直接访问对应的形式单元

传地址

1
2
3
4
把实参的地址传递给相应的形参
实现方法
调用过程把实参的地址传递到被调用过程相应的形式单元中
被调用过程中,对形参的引用或赋值被处理成对形式单元的间接访问

传值结果

1
2
3
4
5
传地址的一种变形
实现方法
每个形参对应两个形式单元。第一个形式单元存放实参的地址,第二个形式单元存放实参的值
在过程体中,对形参的引用或赋值看作对它的第二个形式单元的直接访问
过程完成返回前,把第二个单元的内容存放到第一个单元所指的实参单元中

传名

1
2
3
4
相当于把被调用过程的过程体抄到调用出现的地方,但把其中出现的形参都替换成相应的实参
实现方法
在进入被调用过程之前不对实参预先进行计值,而是让过程体中每当使用到相应的实参时才逐次对它实行计值(或计算地址)
通常把实参处理成一个子程序(称为参数子程序),每当过程体中使用到相应的实参时就调用这个子程序

符号表

符号表是用于存放标识符的属性信息的数据结构

1
2
3
4
5
种属 (Kind)
类型 (Type)
存储位置、长度
作用域
参数和返回值信息

符号表的作用

1
2
辅助代码生成
一致性检查

例子

image-20220514213155111

标识符的基本处理方法

1
2
3
4
5
6
当在某一层的声明语句中识别出一个标识符(id的定义性出现)时,以此标识符查相应于本层的符号表
如果查到,则报错并发出诊断信息“id重复声明”
否则,在符号表中加入新登记项,将标识符及有关信息填入
当在可执行语句部分扫视到标识符时( id的应用性出现)
首先在该层符号表中查找该id,如果找不到,则到直接外层符号表中去查,如此等等,一旦找到,则在表中取出有关信息并作相应处理
如果查遍所有外层符号表均未找到该id,则报错并发出诊断信息“id未声明”

符号表的建立?

代码优化

流图

基本块(Basic Block)是满足下列条件的最大的连续三地址指令序列

1
2
控制流只能从基本块的第一条指令进入该块。也就是说,没有跳转到基本块中间或末尾指令的转移指令
除了基本块的最后一条指令,控制流在离开基本块之前不会跳转或者停机

每个基本块由一组总是一起执行的指令组成

image-20220515003940960

流图的每个结点是一个基本块
从基本块B到基本块C之间有一条边当且仅当基本块C的第一条指令可能紧跟在B的最后一条指令之后执行,此时称B是C的前驱(predecessor) , C是B的后继(successor)

优化的分类

机器无关优化:针对中间代码
机器相关优化:针对目标代码
局部代码优化:单个基本块范围内的优化
全局代码优化:面向多个基本块的优化

常用的优化方法

1
2
3
4
5
删除公共子表达式
删除无用代码
代码移动
强度削弱
删除归纳变量

删除公共子表达式

如果表达式x op y先前已被计算过,并且从先前的计算到现在,x op y中变量的值没有改变,那么x op y的这次出现就称为公共子表达式

局部公共子表达式;全局公共子表达式

例子

删除无用代码

复制传播

1
2
常用的公共子表达式消除算法和其它一些优化算法会引入一些复制语句(形如x = y的赋值语句)
复制传播:在复制语句x = y之后尽可能地用y代替x

复制传播给删除无用代码带来机会

无用代码(死代码Dead-Code ) :其计算结果永远不会被使用的语句

例子

常量合并

如果在编译时刻推导出一个表达式的值是常量,就可以使用该常量来替代这个表达式。该技术被称为常量合并

代码移动

这个转换处理的是那些不管循环执行多少次都得到相同结果的表达式(即循环不变计算,loop-invariant computation) ,在进入循环之前就对它们求值

对于多重嵌套的循环,循环不变计算是相对于某个循环而言的。可能对于更加外层的循环,它就不是循环不变计算

强度削弱

用较快的操作代替较慢的操作,如用加代替乘

归纳变量

1
对于一个变量x ,如果存在一个正的或负的常数c使得每次x被赋值时它的值总增加c ,那么x就称为归纳变量(Induction Variable)

删除归纳变量

1
在沿着循环运行时,如果有一组归纳变量的值的变化保持步调一致,常常可以将这组变量删除为只剩一个

基本块的优化

很多重要的局部优化技术首先把一个基本块转换成为一个无环有向图

image-20220515144138737

基于基本块的 DAG 删除无用代码

1
从一个DAG上删除所有没有附加活跃变量(活跃变量是指其值可能会在以后被使用的变量)的根结点(即没有父结点的结点) 。重复应用这样的处理过程就可以从DAG中消除所有对应于无用代码的结点

image-20220515144511396

数组元素赋值指令的表示

image-20220515144602509

1
在a[j]=y时,有可能改变a[i]的值

image-20220515144738742

根据基本块的DAG可以获得一些非常有用的信息

1
2
3
4
确定哪些变量的值在该基本块中赋值前被引用过
在DAG中创建了叶结点的那些变量
确定哪些语句计算的值可以在基本块外被引用
在DAG构造过程中为语句s(该语句为变量x定值)创建的节点N,在DAG构造结束时x仍然是N的定值变量

image-20220515144412561

例子

数据流分析

一组用来获取有关数据如何沿着程序执行路径流动的相关信息的技术

在每一种数据流分析应用中,都会把每个程序点和一个数据流值关联起来

数据流分析的主要应用

1
2
3
到达-定值分析 (Reaching-Definition Analysis)
活跃变量分析 (Live-Variable Analysis)
可用表达式分析 (Available-Expression Analysis)

数据流分析模式

1
2
3
4
5
6
7
8
语句的数据流模式
IN[s]: 语句s之前的数据流值
OUT[s]: 语句s之后的数据流值
fs:语句s的传递函数(transfer function)
一个赋值语句s之前和之后的数据流值的关系
传递函数的两种风格
信息沿执行路径前向传播 (前向数据流问题):OUT[s] = fs (IN[s])
信息沿执行路径逆向传播 (逆向数据流问题):IN[s] = fs (OUT[s])

到达定值分析

定值

1
变量x的定值是(可能)将一个值赋给x的语句

到达定值(Reaching Definition)

1
2
如果存在一条从紧跟在x的定值d后面的点到达某一程序点p的路径,而且在此路径上d没有被“杀死” (如果在此路径上有对变量x的其它定值d′,则称定值d被定值d′“杀死”了) ,则称定值d到达程序点p
直观地讲,如果某个变量x的一个定值d到达点p,在点p处使用的x的值可能就是由d最后赋予的

image-20220515155110137

到达定值分析的主要用途

循环不变计算的检测

1
如果循环中含有赋值x=y+z ,而y和z所有可能的定值都在循环外面(包括y或z是常数的特殊情况) ,那么y+z就是循环不变计算

常量合并

1
如果对变量x的某次使用只有一个定值可以到达,并且该定值把一个常量赋给x ,那么可以简单地把x替换为该常量

判定变量x在p点上是否未经定值就被引用

image-20220515155325874

image-20220515155539821

image-20220515155645902

例子

image-20220515155911362

到达定值的计算

例题

引用-定值链

image-20220515160301603

活跃变量分析

活跃变量

1
对于变量x和程序点p,如果在流图中沿着从p开始的某条路径会引用变量x在p点的值,则称变量x在点p是活跃(live)的,否则称变量x在点p不活跃(dead)

例子

活跃变量信息的主要用途

删除无用赋值

1
无用赋值:如果x在点p的定值在基本块内所有后继点都不被引用,且x在基本块出口之后又是不活跃的,那么x在点p的定值就是无用的

为基本块分配寄存器

1
2
如果所有寄存器都被占用,并且还需要申请一个寄存器,则应该考虑使用已经存放了死亡值的寄存器,因为这个值不需要保存到内存
如果一个值在基本块结尾处是死的就不必在结尾处保存这个值

image-20220515165840678

image-20220515170431350

image-20220515170613886

image-20220515172411560

image-20220515173505087

可用表达式分析

可用表达式

1
如果从流图的首节点到达程序点 p的每条路径都对表达式x op y进行计算,并且从最后一个这样的计算到点p之间没有再次对x或y定值,那么表达式x op y在点 p是可用的(available)

表达式可用的直观意义

1
在点 p上,x op y已经在之前被计算过,不需要重新计算

主要通途

消除全局公共子表达式

进行复制传播

image-20220515193957942

可用表达式传递函数

image-20220515194252677

可用表达式的数据流方程

image-20220515194545925

image-20220515194801190

注意此处初始化

流图中的循环

支配结点

1
如果从流图的入口结点到结点n的每条路径都经过结点d,则称结点d支配(dominate)结点n,记为d dom n

寻找支配节点

image-20220515195118328

image-20220515195158344

回边

1
如果存在从结点n到d的有向边n→d,且d dom n,那么这条边称为回边

自然循环

image-20220515195547361

image-20220515195949826

image-20220515200001241

自然循环的一个重要性质

1
如果两个自然循环的首结点不相同,则这两个循环要么互不相交,要么一个完全包含(嵌入)在另外一个里面

最内循环 (Innermost Loops): 不包含其它循环的循环

如果两个循环具有相同的首结点,那么很难说哪个是最内循环。此时把两个循环合并

全局优化

1
2
3
4
5
删除全局公共子表达式
删除复制语句
代码移动
作用于递归变量的强度削弱
删除递归变量

删除全局公共子表达式

image-20220515200350777

删除复制语句

对于复制语句s: x=y,如果在x的所有引用点都可以用对y的引用代替对x的引用(复制传播),那么可以删除复制语句 x=y

image-20220515200456345

代码移动

循环不变计算检测算法

image-20220515200548207

代码外提

image-20220515200759125

循环不变计算语句 s : x = y + z 移动的条件

1
2
3
(1) s所在的基本块是循环所有出口结点(有后继结点在循环外的结点)的支配结点
(2) 循环中没有其它语句对x赋值
(3) 循环中对x的引用仅由s到达

image-20220515201036529

例子

作用于归纳变量的强度削弱

1
2
3
4
对于一个变量x ,如果存在一个正的或负的常量c ,使得每次x被赋值时,它的值总是增加c ,则称x为归纳变量
如果循环L中的变量i 只有形如i =i+c的定值(c是常量),则称i为循环L的基本归纳变量
如果j = c×i+d,其中i是基本归纳变量,c和d是常量,则j也是一个归纳变量,称j属于i族
每个归纳变量都关联一个三元组。如果j = c×i+d,其中i是基本归纳变量,c和d是常量,则与j相关联的三元组是( i, c, d )

image-20220515201237286

image-20220515201248830

image-20220515201356302

归纳变量的删除

1
2
3
对于在强度削弱算法中引入的复制语句j=t,如果在归纳变量j的所有引用点都可以用对t的引用代替对j的引用,并且j在循环的出口处不活跃,则可以删除复制语句j=t

强度削弱后,有些归纳变量的作用只是用于测试。如果可以用对其它归纳变量的测试代替对这种归纳变量的测试,那么可以删除这种归纳变量

删除仅用于测试的归纳变量

image-20220515211020194

代码生成

代码生成器的主要任务

指令选择

1
选择适当的目标机指令来实现中间表示(IR)语句

寄存器分配(allocation)和指派(assignment)

1
把哪个值放在哪个寄存器中

指令排序

1
按照什么顺序来安排指令的执行

一个简单的目标机模型

三地址机器模型

1
2
3
4
5
加载、保存、运算、跳转等操作
内存按字节寻址
n个通用寄存器R0, R1, …, Rn-1
假设所有的运算分量都是整数
指令之间可能有一个标号

指令选择

image-20220515215146285

过程调用和返回的目标代码

1
2
使用静态内存分配的方式
使用栈式内存分配的方式

callee的活动记录在静态区中的起始位置

callee的目标代码在代码区中的起始位置

image-20220515215844342

寄存器的选择

image-20220515220019625

寄存器描述符和地址描述符

寄存器描述符

1
记录每个寄存器当前存放的是哪些变量的值

地址描述符

1
2
3
记录运行时每个名字的当前值存放在哪个或哪些位置
该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合
这些信息可以存放在该变量名对应的符号表条目中

基本块的收尾处理

1
2
3
在基本块结束之前,基本块中使用的变量可能仅存放在某个寄存器中
如果这个变量是一个只在基本块内部使用的临时变量,当基本块结束时,可以忘记这些临时变量的值并假设这些寄存器是空的
对于一个在基本块的出口处可能活跃的变量x , 如果它的地址描述符表明它的值没有存放在x的内存位置上, 则生成指令“ST x, R” ( R是在基本块结尾处存放 x值的寄存器 )

管理寄存器和地址描述符

1
当代码生成算法生成加载、保存和其他指令时,它必须同时更新寄存器和地址描述符

image-20220515220152288

image-20220515220242413

image-20220515220310043

image-20220515220624081

寄存器选择函getReg

image-20220515221133482

image-20220515221317333

image-20220515221332913

窥孔优化

窥孔(peephole)是程序上的一个小的滑动窗口

窥孔优化是指在优化的时候,检查目标指令的一个滑动窗口(即窥孔) ,并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列

也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量

具有窥孔优化特点的程序变换的例子

1
2
3
4
冗余指令删除
控制流优化
代数优化
机器特有指令的使用

习题总结

重点

已掌握

1
2
3
4
3.1 4.1 4.2  5.1(5.1.2重点) 6.1 6.2 7.1 7.2 7.3 7.4 7.5 (规范LR项集族) 7.6 7.7 7.8  7.9
8.1 8.3 9.2(设计SDD) 9.3(设计SDD) 9.4(改写SDT) 12.2(四元式) 12.3(翻译赋值语句) 13.1(控制流处理方案) 13.2 13.3(控制流四元式) 14.1(求truelist) 14.2 14.3 14.4(构造SDT) 14.6(设计sdt) 15.1 15.2(快排) 15.3(Fibonacci) 15.4(栈问题,考前再看一下) 15.5 15.6(符号表) 16.3 16.4(DAG) 16.5 16.6(带跳转和[]=的DAG) 16.7 16.8(基本块)
17.1(到达定值分析) 18.1(可用表达式分析) 18.2(活跃变量分析,逆分析) 18.3(到达定值分析应用) 19.1(重点,各种值的找取)
19.2(重点,代码优化) 19.6

未掌握

1
2
3
4
5
6
4.1.3的消除左递归方法 
9.1 扩展SDD
10.1(构造递归下降SDD)
13.4 13.5 *13.6(翻译方案)
14.5(超级复杂的SDT构造)
19.5

非重点

已掌握

1
1.2 2.1 8.2 8.4(是否存在一致的求值过程)

未掌握

1
1.1 6.3 18.4 18.5

各种链

NLP任务:分词、词性标注、未登录词识别

语言的性质:共时性;历时性

语法单位

1
2
3
4
句子是语言中最大的语法单位
词组是词的组合,它是句子里面作用相当于词而本身又是由词组成的大于词的单位。
词是最重要的一级语法单位,它是造句的时候能够独立运用的最小单位。
语素是语言中音义结合的最小单位。就汉语来说,大抵一个汉字就是一个语素,但是也有两个字表示一个语素的,如:“咖啡”

语料库

• 语料库(corpus)一词在语言学上意指大量的文本,通常经过整理, 具有既定格式与标记

语料库的种类

1
2
共时语料库与历时语料库
通用语料库与专用语料库

语料加工

文本处理

1
2
3
4
5
6
7
8
垃圾格式问题
大小写
标记化
空格
连字符
词法
句子定义—启发式算法
句子边界的研究

格式标注

1
2
3
通用标记语言SGML
SGML是超文本格式的最高层次标准,是可以定义标记语言的元语言
语法标注

Zipf法则 • 一个词地频率f和它的词频排序位置r: f*r=k (k为常数)

image-20211227150000774

如果设置参数B=1, ρ=0,Mandelbrot公式就简化为Zipf法则

搭配抽取

image-20211227150045052

语料库加工_双语句子自动对齐& 双语词典获取

句子对齐问题描述

基于长度的句子对齐  基本思想:源语言和目标语言的句子长度存在一定 的比例关系

要求:最小(句珠内无句珠); 唯一(一个句子仅属于一个句珠); 无交叉(后句对齐一定在前句对齐位置之后)

基于共现的双语词典的获取

基本思想:如果汉语词出现在某个双语句对 中,其译文也必定在这个句对中。

汉英词典的迭代获取策略

1
2
3
4
5
6
7
8
迭代策略
1) 初始化;
2) 使用对数相似性模型计算汉英翻译词对候选;
3) 选取前n个汉英对译词对;
4) 双语句对中剔除选定的翻译词对;
5) 若不满足终止条件,重复步骤2;
 几点说明:复合词暂未考虑;可加入交互方式;

基于共现的词汇对译模型

评价方式:专家独立于上下文进行判别

1
2
评价1:每5000个翻译词对候选中正确的译文数
评价2:综合考虑翻译词典的性能

汉语自动分词

词法分析

词干提取vs词形还原:分别用于IR 和 NLP

1
2
词干提取(stemming)是抽取词的词干或词根形式(不一定能够表达完整语义
词形还原(lemmatization),是把一个任何形式的语言词汇还原为一般形式(能表达完整语义)
1
2
3
4
词干提取主要是采用“缩减”的方法
词形还原主要采用“转变”的方法
在复杂性上:词干提取方法相对简单,词形还原更复杂
在实现方法上:主流方法类似,但具体实现上各有侧重

词性标注

1
2
3
4
5
6
词性标注(part-of-speech tagging),又称为词类标注或者简称
标注,是指为分词结果中的每个单词标注一个正确的词性的程序,
也即确定每个词是名词、动词、形容词或者其他词性的过程
• 词性标注是很多NLP任务的预处理步骤,如句法分析,经过词性
标注后的文本会带来很大的便利性,但也不是不可或缺的步骤

分词算法

正向最大匹配分词(Forward Maximum Matching method, FMM)

1
2
3
4
5
6
7
8
9
基本思想:将当前能够匹配的最长词输出
• 1. 设自动分词词典中最长词条所含汉字个数为I
• 2. 取被处理材料当前字符串序数中的I个字作为匹配字段,查找分词词典。
若词典中有这样的一个I字词,则匹配成功,匹配字段作为一个词被切分出
来,转6
• 3. 如果词典中找不到这样的一个I字词,则匹配失败
• 4. 匹配字段去掉最后一个汉字,I--
• 5. 重复2-4,直至切分成功为止
• 6. I重新赋初值,转2,直到切分出所有词为止

逆向最大匹配分词(Backward Maximum Matching method, BMM法

1
2
3
分词过程与FMM方法相同,不过是从句子(或文
章)末尾开始处理,每次匹配不成功时去掉的是
最前面的一个汉字

实验表明:逆向最大匹配法比最大匹配法更有效

最大匹配法的问题

1
2
3
• 存在分词错误:增加知识、局部修改
• 局部修改:增加歧义词表,排歧规则
无法发现分词歧义->从单向匹配改为双向最大匹配

双向匹配法(Bi-direction Matching method, BM法)

1
2
3
双向最大匹配法是将正向最大匹配法(FMM)得到的分词
结果和逆向最大匹配法(BMM)得到的结果进行比较,从
而决定正确的分词方法

最少分词法

1
2
3
4
5
6
7
8
9
10
11
• 分词结果中含词数最少
• 优化代替了贪心
• 等价于最短路径
•算法:
• 动态规划算法
• 优点:好于单向的最大匹配方法
• 最大匹配:独立自主/和平/等/互利/的/原则
• 最短路径:独立自主/和/平等互利/的/原则
• 缺点:忽略了所有覆盖歧义,也无法解决大部分交叉歧义
• 结合成分子时
• 结合|成分|子 {} 结|合成|分子 {} 结合|成|分

分词问题:歧义

交集型切分歧义

1
2
汉字串AJB被称作交集型切分歧义,如果满足AJ、JB同时
为词(A、J、B分别为汉字串)。此时汉字串J被称作交集串。

组合型切分歧义

1
2
• 汉字串AB被称作组合型切分歧义,如果满足条件:A、
B、AB同时为词

交集型歧义字段中含有交集字段的个数,称为链长

“真歧义”和“伪歧义”

1
2
• 真歧义指存在两种或两种以上的可实现的切分形式
• 伪歧义一般只有一种正确的切分形式

分词问题

1
2
3
4
歧义
未登录词
新词

分词质量评价

image-20211227193857156

中文分词_统计建模

基于N元文法的分词(MM)

MM(马尔可夫模型/过程) :有限历史假设,仅依 赖前n-1个词

一种最简化的情况:一元文法

1
2
3
4
5
6
P(S)=p(w1) ·p(w2) ·p(w3)….p(wn)
 等价于最大频率分词
 即把切分路径上每一个词的概率相乘得到该切
分路径的概率
 把词概率的负对数理解成路径“代价”,输出
结果就是整体代价最“小”分词序列

采用二元语法(bi-gram):性能进一步提高

image-20211227195204331

 更大的n:对下一个词出现的约束性信息更多,更大的辨别力。  更小的n:出现的次数更多,更可靠的统计结果,更高的可靠性。

等价类映射:降低语言模型参数空间

数据平滑(smoothing):保持模型的辨别能力

基于HMM的分词/词性标注一体化

输入:待处理句子S

输出:S的 词序列 W = w1 ,w2…wn

词性序列 T = t1 ,t2…tn

提示  W可以代表S  分词结果即观测序列  词性序列是状态序列

公式推导

image-20211227200001707

image-20211227200011651

image-20211227200200077

由字构词的汉语分词方法

基本思路  分词过程:一个字的分类问题;  每个字在词语中属于一个确定位置

字的的标注过程中,对所有的字根据预定义的特 征进行词位特征学习,获得一个概率模型

由字构词的分词技术的优势

1
 简化了分词系统的设计  文本中的词表词和未登录词都是用统一的字 标注过程来实现的,分词过程成为字重组的 简单过程。  既可以不必专门强调词表词信息,也不用专 门设计特定的未登录词识别模块

汉语分词方法的后处理方法

为什么不采用更精巧的模型?

1
四元或更高阶...  不可行,需要大量的参数  不得不做一些平滑或差值  难度随模型复杂度而加剧

两个重要组成部分:

1
2
 允许的错误校正转换的详细说明
 学习算法

输入数据

1
2
一个已经标注好的语料库,
*一个词典

基于转换错误驱动的规则方法

1
2
3
4
5
6
 学习和标注在该方法种都是简单和直观的
 成功用于词性标注、句法分析、介词附着以及
语义消歧
 经验上,没有出现过拟合现象
 可以被用来解决大部分后处理问题
 效率的提升优化,考验工程能力

标注可以采用

1
 隐马尔科夫模型(HMM)  最大熵(ME)  最大熵马尔科夫模型(MEMM)  条件随机场(CRF)等

隐马尔科夫模型

马尔科夫(Markov)模型

马尔科夫模型是一种统计模型,广泛的应用在语音识别, 词性自动标注,音字转换,概率文法等各个自然语言处理 的应用领域。

随机过程又称为随机函数,是随时间随机变化的过程。马 尔科夫模型描述了一类重要随机过程。

系统在时间t处于状态𝑠𝑗的概率取决于其在时间1,2,…t-1的 状态,该概率为:

1
𝑃(𝑞𝑡 = 𝑠𝑗|𝑞𝑡−1 = 𝑠𝑖, 𝑞𝑡−2 = 𝑠𝑘, … )

离散的一阶马尔科夫链:系统在时间t的状态只与时间t-1 的状态有关。

1
𝑃(𝑞𝑡 = 𝑠𝑗|𝑞𝑡−1 = 𝑠𝑖, 𝑞𝑡−2 = 𝑠𝑘, … ) = 𝑃(𝑞𝑡 = 𝑠𝑗|𝑞𝑡−1 = 𝑠𝑖)

状态转移概率𝑎𝑖𝑗必须满足以下条件:

image-20211227203707059

N个状态的一阶马尔科夫过程有𝑁2,可以表示成为一个状 态转移矩阵

eg:状态𝑠1:名词 状态𝑠2:动词 状态𝑠3:形容词

如果在该文字中某句子的第一个词为名词,那么该句子 中三类词出现顺序为O=“名动形名”的概率。

image-20211227203903492

马尔科夫(Markov)模型:有限状态机

1
2
3
4
5
6
7
马尔科夫模型可视为随机的有限状态机。
圆圈表示状态,状态之间的转移用带箭头的弧表示,弧上
的数字为状态转移的概率。
初始状态用标记为start的输入箭头表示。
假设任何状态都可作为终止状态。
对每个状态来说,发出弧上的概率和为1。

eg:

image-20211227204121800

一般地,一个HMM记为一个五元组μ=(S,K, A,B,π),其中,S为状态的集合,K为输出符 号的集合,π,A和B分别是初始状态的概率分布、 状态转移概率和符号发射概率。为了简单,有时也将其记为三元组μ=(A,B,π)

隐马尔可夫模型:三个基本问题

1
2
3
4
5
6
7
8
9
10
1.估值问题:给定一个观察序列 O = 𝑂1𝑂2 … 𝑂𝑇 和模型μ=(A,
B,π),如何快速地计算出给定模型μ情况下,观察序列O的
概率,即𝑃 𝑂 𝜇 ?
2.序列问题:给定一个观察序列 O = 𝑂1𝑂2 … 𝑂𝑇 和模型μ=(A,
B,π),如何快速有效的选择在一定意义下“最优”的状态序
列 𝑄 = 𝑞1𝑞2 … 𝑞𝑇 ,使得该状态序列“最好的解释”观察序列?
3.参数估计问题:给定一个观察序列O = 𝑂1𝑂2 … 𝑂𝑇,如何根
据最大似然估计来求模型的参数值?即如何调节模型μ=(A,
B,π)的参数,使得𝑃 𝑂 𝜇 最大?

隐马尔可夫模型:求解观察序列的概率

1
给定观察序列O = 𝑂1𝑂2 … 𝑂𝑇和模型𝜇 =(𝐴, 𝐵, π),快速的计算出给定模型𝜇情况下观察序列O的概率,即𝑃 (𝑂|𝜇) 。

image-20211227210645264

隐马尔可夫模型:前向算法

1
基本思想:定义前向变量𝛼𝑡(𝑖),前向变量𝛼𝑡(𝑖)是在时间t,HMM输出了序列𝑂1𝑂2 … 𝑂𝑡 ,并且位于状态𝑠𝑖的概率。

image-20211227211103464

前向算法总的复杂度为O(𝑁2𝑇)

隐马尔可夫模型:后向算法

1
后向变量𝛽𝑡(𝑖)是在给定模型𝜇 = (𝐴, 𝐵, π),并且在时间t状态为𝑠𝑖的条件下,HMM输出观察序列𝑂𝑡+1 … 𝑂𝑇的概率。

与计算前向变量一样,可以用动态规划的算法计算后向变量。

image-20211227211441031

时间复杂度:O(𝑁2𝑇)

序列问题

隐马尔可夫模型:维特比算法

1
2
3
4
维特比算法用于求解HMM中的第二个问题,给定一个观
察序列O = 𝑂1𝑂2 … 𝑂𝑇和模型𝜇 = (𝐴, 𝐵, π),如何快速有效
的选择在一定意义下最优的状态序列𝑄 = 𝑞1𝑞2 … 𝑞𝑇,使得
该状态序列“最好的解释”观察序列。

image-20211227211917788

image-20211227211938609

存在问题

1
单独最优不一定整体最优

参数估计

最 大似然估计

EM

句法分析

句法分析概述

基本任务:确定句子的句法结构或句子中词汇之间的依存关系。

定义:判断单词序列(一般为句子)判读其构成是否合乎 给定的语法(recognition),如果是,则给出其(树)结构 (parsing)

描述一种语言可以有三种途径

1
2
3
穷举法:把语言中的所有句子都枚举出来。显然,这种方法只适合句子数目有限的语
语法/文法描述:语言中的每个句子用严格定义的规则来构造,利用规则生成语言中合法的句子
自动机法:通过对输入句子进行合法性检验,区别哪些是语言中的句子,哪些不是语言中的句子

形式语法

1
2
3
4
5
四元组 𝐺 = {𝑁, Σ, 𝑃, 𝑆}
𝑁是非终结符(non-terminal symbol)的有限集合(有时也称变量集或句法种类集)
Σ是终结符号(terminal symbol)的有限集合,𝑁 ∩ Σ = ∅
𝑃是一组重写规则的有限集合:𝑃 = 𝛼 → 𝛽 ,其中𝛼, 𝛽是由V中元素构成的串,但是𝛼中至少应含一个非终结符
𝑆 ∈ 𝑁称为句子符或初始符

形式语法种类

1
2
3
4
正则文法
上下文无关文法
上下文相关文法
无约束文法

控制策略

1
2
3
4
5
自顶向下、自底向上
移进-归约是自底向上语法分析的一种形式
 使用一个栈来保存文法符号,并用一个输入缓冲区来存放将要进行语
法分析的其余符号

搜索策略

1
深搜广搜

扫描策略

1
自左至右,自右至左

移进-归约是自底向上语法分析的一种形式

CFG缺陷

1
2
3
4
5
6
7
8
9
10
 对于一个中等长度的输入句子来说,要利用大覆盖度的语法规
则分析出所有可能的句子结构是非常困难的,分析过程的复杂
度往往使程序无法实现
 即使能分析出句子所有可能的结构,也难以在巨大的句法分析
结果集中实现有效的消歧,并选择出最有可能的分析结果
 手工编写的规则一般带有一定的主观性,对于实际应用系统来
说,往往难以覆盖大领域的所有复杂语言
 写规则本身是一件大工作量的复杂劳动,而且编写的规则对特
定的领域有密切的相关性,不利于句法分析系统向其他领域移

概率上下文无关文法(PCFG)

概率上下文无关文法就是一个为规则增添了概率的简单CFG, 指明了不同重写规则的可能性大小

在基于PCFG的句法分析模型中,假设满足以下三个条件:

1
2
3
上下文无关性
祖先无关性
位置不变性

剪枝策略:Beam search(集束搜索)

1
2
3
4
一种启发式图搜索算法,为了减少搜索占用的时间和空间,在每一步深度扩展的时候,
减掉一些质量比较差的节点,保留质量较高的一些节点
优点是减少空间消耗,提高时间效率
缺点是有可能存在潜在的最佳方案被丢弃,beam search算法是不完全的

PCFG的优点

1
2
3
4
5
可利用概率减少分析过程的搜索空间
可以利用概率对概率较小的子树剪枝,加快分析效

可以定量地比较两个语法的性能

PCFG的缺陷

1
2
结构相关性
词汇相关性

词义消歧

word sense disambiguation WSD

义位:语义系统中能独立存在的基本语义单位

WSD需要解决三个问题:

1
2
3
(1)如何判断一个词是不是多义词? 如何表示一个多义词的不同意思?
(2)对每个多义词,预先要有关于它的 各个不同义项的清晰的区分标准
(3)对出现在具体语境中的每个多义词,为它确定一个合适的义项
1
2
3
4
5
基于机器词典的WSD
基于义类词典的WSD
基于语料库的WSD
基于统计方法的WSD
基于规则的WSD
1
2
3
4
5
6
7
总结:
用词典资源进行词义排歧,是利用词典中对多义
词的各个义项的描写,求多义词的释义跟其上下
文环境词的释义之间的交集,判断词义的亲和程
度,来确定词义;
由于词典释义的概括性,这种方法应用于实际语
料中多义词的排歧,效果不一定理想

基于义类词典的WSD方法

image-20211227233833336

互信息:I(X;Y)反映的是在知道了Y的值 以后X的不确定性的减少量。

基于Bayes判别的WSD方法

image-20211227235729108

词义消歧——基于多分类器集成

1
2
3
4
5
6
总结
还有很多问题需要探讨
❖如何选用更有效的分类器
❖单分类器的结果怎样更高效地集成
❖如何在单分类器中选取更有效的特征
 集成学习的研究对自然语言处理中的其他任务

篇章

概念

1
2
3
4
5
Anaphor:指代语
Entity(referent):实体(指称对象)
Reference:指称。用于指称实体的语言表示
Antecedent:先行语。语篇中引入的一个相对明确的指称意义表述(如张三);
Coreference:共指(同指)。当两种表述均指称相同对象(实体)时,这两种表述具有共指关系

六类指称表示

1
2
3
4
5
6
7
 Indefinite NPs(不定名词): 一辆汽车
 Definite NPs (有定名词): 那个人
 Pronouns (人称代词): 它,他
 Demonstratives (指示代词): 这,那
 One-anaphora (one指代): one (in English)
 Zero anaphora (0型指代): 省略

指代一般包括两种情况

1
2
3
4
5
6
7
– 回指(Anaphora):强调指代语与另一个表述之间的关
系。指代语的指称对象通常不明确,需要确定其与先行
语之间的关系来解释指代语的语义
• 张先生走过来,给大家看他的新作品
– 共指(coreference):强调一个表述与另一个表述是否
指向相同的实体,可以独立于上下文存在
• 第44任美国总统 与奥巴马

衔接和连贯

以词汇表示的关联,通常称为“衔接(cohesion),强调其构成成分

通过句子意义表示的关联称为连贯Coherence,强调整体上表达某种意义

篇章表示和相似度计算

将文档表示为如下所示的向量: 𝑑𝑗 = (𝑤1,𝑗 , 𝑤2,𝑗 , 𝑤3,𝑗 , … , 𝑤𝑡,𝑗)  向量的每一维都对应于词表中的一个词。  如果某个词出现在了文档中,那它在向量中的值就非 零。  这个值有很多计算方法,我们使用词语在文档中出现 的次数表示。

机器翻译

传统机器翻译方法

1
直接翻译法

基于规则的翻译方法

1
2
3
对源语言和目标语言均进行适当描述
吧翻译机制与语法分开
用规则描述语法的翻译方式
1
2
3
4
5
6
▪优点:
▪ 可以较好地保持原文的结构,产生的译文结构与源文的结构关系密切
▪ 尤其对于语言现象的或句法结构的明确的源语言语句具有较强的处理能力
▪弱点:
▪ 规则一般由人工编写,工作量大,主观性强,一致性难以保障
▪ 不利于系统扩充,对非规范语言现 象缺乏相应的处理能力

基于实例的翻译方法

1
方法:输入语句->与事例相似度比较->翻译结果
1
2
3
4
5
6
7
8
▪ 方法优点
▪ 不要求源语言句子必须符合语法规定;
▪ 翻译机制一般不需要对源语言句子做深入分析;
▪ 方法弱点
▪ 两个不同的句子之间的相似性(包括结构相似性和语义相似性)往往难以把握
▪ 在口语中,句子结构一般比较松散,成分冗余和成分省略都较严重;
▪ 系统往往难以处理事例库中没有记录的陌生的语言现象;
▪ 当事例库达到一定规模时,其事例检索的效率较低;

基于统计的机器翻译模型

噪声信道模型

1
一种语言T 由于经过一个噪声信道而发生变形从而在信道的另一端呈现为另一种语言 S

翻译问题可定义为:

1
▪ 如何根据观察到的 S,恢复最为可能的T 问题。

image-20211228101907190

▪三个关键问题 ▪ (1)估计语言模型概率 p(T); ▪ (2)估计翻译概率 p(S|T); ▪ (3)快速有效地搜索T 使得 p(T)×p(S | T) 最大

基于词的统计机器翻译模型

IBM模型1:词汇翻译(词对齐)

1
2
3
4
5
6
7
8
▪ 基于词的统计翻译模型
▪ 引入了词对齐的问题
▪ 通过EM算法学习词对齐
▪ 缺陷
▪ 无法刻画翻译过程中重排序、添词、舍词等情况;
▪ 例如:
▪ Seldom do I go to work by bus.
▪ 我很少乘公共汽车上班

IBM模型2:增加绝对对齐模型

IBM模型3:引入繁衍率模型

1
2
3
前述模型存在的问题
▪ 在随机选择对位关系的情况下,与目标语言句子中的单词t对应的源语言句子中的单
词数目是一个随机变量;

繁衍率

1
2
3
4
定义:与目标语言句子中的单词t对应的源语言句子中的单词数目的变量
▪ 记做Фt,称该变量为单词t的繁衍能力或产出率(fertility)。一个具体的取值记做:Фt
▪ 繁衍率刻画的是目标语言单词与源语言单词之间一对多的关系

基于短语的统计机器翻译模型

基本思想

1
2
3
4
5
▪ 把训练语料库中所有对齐的短语及其翻译概率存储起来,作为一部带
概率的短语词典
▪ 这里所说的短语是任意连续的词串,不一定是一个独立的语言单位
▪ 翻译的时候将输入的句子与短语词典进行匹配,选择最好的短语划分,
将得到的短语译文重新排序,得到最优的译文.

系统融合

几个相似的系统执行同一个任务时,可能有多个输出结果,系统融合将这些结果进行融 合,抽取其有用信息,归纳得到任务的最终输出结果。

目标:最终的输出比之前的输入结果都要好

句子级系统融合

1
2
两种技术
最小贝叶斯风险解码;通用线性模型

句子级系统融合方法不会产生新的翻译句子,而是在已有的翻 译句子中挑选出最好的一个

短语级系统融合 ▪ 利用多个翻译系统的输出结果,重新抽取短语翻译规则集合,并利用 新的短语翻译规则进行重新解码

1
2
3
基本思想:首先合并参与融合的所有系统的短语表,从中抽取
一个新的源语言到目标语言的短语表,然后使用新的短语表和
语言模型去重新解码源语言句子。

词语级系统融合 ▪ 首先将多个翻译系统的译文输出进行词语对齐,构建一个混淆网络, 对混淆网络中的每个位置的候选词进行置信度估计, 最后进行混淆网 络解码

小结

1
2
3
4
5
6
7
8
9
10
11
句子级系统融合
▪ 未生成新的翻译假设,有效的保护原来翻译假设中短语的连续性和句子词序,但
是也没有吸收借鉴其他翻译假设中词或者短语层次的知识。
▪ 短语级系统融合
▪ 借鉴其他翻译系统的短语表知识,利用传统的基于短语的翻译引擎来重新解码源
语言的句子。有效的保持短语的连续性和译文的局部词序。但是不能很好的利用
非连续短语和句法知识来克服译文的远距离调序问题
▪ 词语级系统融合
▪ 从词的粒度重组了输出译文,充分利用了各个翻译假设的词汇级别的知识,取长
补短。但是在混淆网络解码时,并不能保证新生成的翻译句子的词序一致性和短
语连续性

应用:语言自动生成

自然语言生成概述

NLG生成模型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1. 马尔可夫链:通过当前单词可以预测句子中的下一个单
词。
缺点:无法探测当前单词与句子中其他单词的关系以及句
子的结构,使得预测结果不够准确。
2. 循环神经网络(RNN):通过前馈网络传递序列的每个项目
信息,并将模型的输出作为序列中下一项的输入,每个项
目存储前面步骤中的信息。
优点:能够捕捉输入数据的序列特征
缺点:第一,RNN短期记忆无法生成连贯的长句子;第二,
因为 RNN 不能并行计算,无法适应主流趋势。
3. 长短期记忆网络(LSTM),解决梯度消失问题,但难以并行化
4. Seq2Seq,能够解决大部分序列不等长的问题
5. Attention模型
6. Transformer模型,能够在不考虑单词位置的情况
下,直接捕捉句子中所有单词之间的关系
7. ELMO模型
8. BERT模型

数据到文本的生成

以包含键值对的数据作为输入,旨在 自动生成流畅的、贴近事实的文本以描 述输入数据。

1
2
3
4
 信号分析模块(Siganl Analysis)
 数据阐释模块(Data Interpretation)
 文档规划模块(Document Planning)
 微规划与实现模块(Microplanning and Realisation)

应用领域:

1
2
3
4
5
6
 天气预报领域的文本生成系统
 针对空气质量的文本生成系统
 针对财经数据的文本生成系统
 面向医疗诊断数据的文本生成系统
 基于体育数据生成文本摘要

文本到文本的生成

对给定文本进行变换和处理从而获得新文本的技术

应用

1
2
3
4
5
 对联自动生成
 诗歌自动生成
 作文自动生成
 对话生成*---这个任务现阶段一般不作为NLG的研究分支来探讨

词和文档表示与相似度计算

词的表示

独热表示

1
每个词对应一个向量,向量的维度等于词典的大小,向量中只有一个元素值为1,其余的元素均为0 ,值为1的元素对应的下标为该词在词典中的位置

词频 -逆文档频率(TF -IDF)

词嵌入方法的问题

1
2
3
4
5
6
静态词向量
词向量无法随语境变化
不能处理一词多义
多义词无法区分多个含义
不能有效区分反义词
反义词的上下文很相似

词向量

skip-gram

1
2
3
4
5
6
7
1. 将目标词和邻近的 
语境词作为正面例子。
2.随机抽取词库中的其他词
词库中的其他词,以获得负面样本。
3. 使用逻辑回归来训练一个分类器,以区分这两种情况。
区分这两种情况。
4. 使用权重作为嵌入。

文档表示

image-20211228162546651

文本相似度计算

编辑距离,动态规划

信息抽取

信息抽取的定义、任务及发展

信息抽取中的主要任务

1
2
3
4
5
6
7
8
命名实体识别:
识别和分类文本中出现的“实体提及”
实体链接:
将“实体提及”链接到知识库中对应的实体
关系抽取:
找到句子中有关系的两个实体,并识别出他们之间的关系类型
事件抽取:
事件抽取就要是找到一个事件对应的元素。

命名实体识别

挑战

1
2
3
4
5
6
7
8
种类繁多,命名方式灵活多样
同一实体对应很多变体
相同的词或者短语可以表示不同类别的实

存在嵌套
细粒度
语言不断进化,新的挑战不断出现

主要方法

1
基于规则的方法 基于词典的方法 机器学习方法 ◼最大熵 ◼条件随机场 ◼深度学

命名实体识别的评价

image-20211228163639194

image-20211228163649954

实体链接

将“实体提及”链接到知识库中对应的实体

关系抽取

自动识别由一对实体和联系这对实体的关系构成的 相关三元组

预定义关系抽取

1
2
3
4
5
6
任务
给定实体关系类别,给定语料,抽取目标关系对
评测语料(MUC, ACE, KBP, SemEval)
专家标注语料,语料质量高
抽取的目标类别已经定义好

基于神经网络的关系抽取方法

1
2
主要问题:如何设计合理的网络结构,从而捕捉更多的信息,进而更准确的完成关系的抽取
网络结构:不同的网络结构捕捉文本中不同的信息

开放域关系抽取

1
2
3
4
5
6
7
8
9
实体类别和关系类别不固定、数量大
难点问题
 如何获取训练语料
 如何获取实体关系类别
 如何针对不同类型目标文本抽取关系
需要研究新的抽取方法
 基于句法的方法
 基于知识监督的方法

深度学习简介

常用的深度学习模型

1
2
3
4
5
激活函数
深度神经网络(Deep Neural Network, DNN)
卷积神经网络(Convolutional Neural Network,CNN)
循环神经网络 (Recurrent Neural Network, RNN)
注意力机制(Attention Mechanisms)

pooling

1
2
3
4
5
目的:
扩大视野:就如同先从近处看一张图片,然后离远一些再看同一张图片,有些细节就会被忽略。
降维:在保留图片局部特征的前提下,使得图片更小,更易于计算。
平移不变性,轻微扰动不会影响输出。
维持同尺寸,便于后端处理。

深度学习模型的应用

1
2
3
4
5
6
7
8
DBN的应用
基于DBN的问答对挖掘
CNN的应用
关系分类
句子分类
LSTM-RNN的应用
命名实体识别