This is the 7th day of my participation in Gwen Challenge

This article is about the AST abstract syntax tree learning notes, here to make a summary and share, there are weaknesses also hope to be correct ~

Introduction to the

Abstract Syntax Tree is essentially the relationship between an Abstract Syntax Tree of JS objects and virtual nodes, as shown in the following figure:

Correlation algorithm reserve

Pointer to the thought

Find the character in a string that is repeated the most times in succession

// Find the most consecutive repeated character in the string
const str = 'aaaaaaaabbbbbbbbbbbbbbbbbcccccccccdddddd'
// start and end: Pointers
let start = 0, end = 1, maxChar = str[0], maxCharLength = 0
// Loop when the start pointer is in the length range of STR
while (start < str.length){
  // If the two Pointers point to different characters, they are not consecutive characters
  if(str[start] ! == str[end]) {// If the difference between Pointers is greater than the largest contiguous number previously stored
    if (end - start > maxCharLength) {
      maxCharLength = end - start
      maxChar = str[start]
    }
    // let the start pointer catch up with the end pointer
    start = end
  }
  // The end pointer is moved back one bit each time through the loop
  end++
}
console.log(maxChar, maxCharLength) // b 17
Copy the code

recursive

When it comes to “rule repetition,” think recursion

Fibonacci numbers

Related exercises: Output the first 10 Fibonacci numbers recursively

function fn(n) {
  console.count(n)
  return n === 0 || n === 1 ? 1 : fn(n-1) + fn(n-2)}for (let i = 0; i < 10; i++) {
  console.log(fn(i))
}
Copy the code

For example, if fn(9) is executed, fn(8) and fn(7) will be executed, and fn(8) will be executed again. To avoid this duplication of calculation, we can use an object to cache the calculation of a function that has already been performed. As follows:

// Set a cache object to store the value of fn(n)
let cache = {}
function fn(n) {
  console.count(n)
  // If the cache has n attributes
  if (cache.hasOwnProperty(n)) {
    return cache[n]
  } else { // If the cache does not have n, this is the first calculation
    const v = n === 0 || n === 1 ? 1 : fn(n-1) + fn(n-2)
    cache[n] = v
    return v
  }
}
for (let i = 0; i < 10; i++) {
  console.log(fn(i))
}
Copy the code

In the form of conversion

Exercise: Convert arrays [1, 2, 3, [4, 5, [6, 7]], 8] to the object format shown in the following figure

There are two ways to solve this problem

1. Recursive arrays

This method is recursive only if the argument passed to convert is an array

const arr = [1.2.3[4.5]]
function convert(arr) {
  let convertArr = []
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] === 'number') {
      convertArr.push({ 'value': arr[i] })
    } else if (Array.isArray(arr[i])) {
      convertArr.push({ 'children': convert(arr[i]) })
    }
  }
  return convertArr
}
const res = convert(arr)
Copy the code

This is a clever use of the map method, so that the parameters passed to convert2, be they arrays or numbers, are recursive

const arr = [1.2.3[4.5]]
function convert2(item) {
  if (typeof item === 'number') {
    return { 'value': item }
  } else if (Array.isArray(item)) {
    return { 'children': item.map(_item= > convert2(_item)) }
  }
}

const res = convert2(arr)
Copy the code

The stack

Exercises: the string 3 2 [a] [b] [1] into abbabbabb here using the ideas of the stack, prepare two stack, a store number, deposit a temporary string, use a pointer traversal 3 2 [a] [b] [1].

• When the pointer points to a number, the number is pushed onto the number stack
• When the pointer points to zero[, an empty string is pushed onto the string stack
• When the pointer points to a letter, change the item at the top of the string stack to that letter
• When the pointer points to zero]In the string, the top item repeats the number just popped, pops the stack, and splices it to the top of the new stack

The illustration is as follows (duplicate numbers or letters are not taken into account here, they are taken into account in the code)

Code implementation

const str = '3[2[9abc]11[d]]'

/ / pointer
let i = 0
// The part of the string that starts at the pointer position and ends
let restStr = str
// A stack to store numbers
const stackNum = []
// Stack of strings
const stackStr = []

function smartRepeat(templateStr) {
  // Use a while instead of a for loop because I is not always +1
  while (i < str.length - 1) { 
    /* -1 is because the last STR must be]. If it is not -1, then in this case when the pointer points to the last], the top of the numeric stack (3) will be pushed out, and then the top of the string stack (abcabcddDDDDDDDDddd) will be pushed out. The concatenation is repeated three times to the new top of the string stack, but there are no more elements in the string stack, the new top will be undefined */
    restStr = str.substring(i)
    // If it is a number followed by a string beginning with [
    if (/^(\d+)\[/.test(restStr)) {
      // Capture the numeric part
      const nums = restStr.match(/^(\d+)\[/) [1]
      // Push the number onto the number stack
      stackNum.push(nums)
      // Push the empty string onto the string stack
      stackStr.push(' ')
      // The pointer skips the corresponding length, +1 because] is skipped together
      i += nums.length + 1
    } else if (/^(\w+)\]/.test(restStr)) { // If it is a string that begins with a letter immediately after]
      // Capture the letter part
      const str = restStr.match(/^(\w+)\]/) [1]
      // Assign the item at the top of the string stack to the captured letter
      stackStr[stackStr.length - 1] = str
      // Skip the length of the letter
      i += str.length
    } else if (restStr[0= = ='] ') {
      // Unstack the number stack
      const popNum = stackNum.pop()
      // Unstack the string
      const popStr = stackStr.pop()
      // String concatenation
      stackStr[stackStr.length - 1] += popStr.repeat(popNum)
      i++ 
    }
  }
  // The while loop ends with the last element in the stack of digits and the last element in the string stack
  return stackStr[0].repeat(stackNum[0])}const result = smartRepeat(str)
console.log(result) // 9abc9abcddddddddddd9abc9abcddddddddddd9abc9abcddddddddddd
Copy the code

Tips: Repeat is the string method of ES6 that constructs and returns a new string containing a specified number of copies of the string to be concatenated together. If the argument of the repeat is a string, it is converted to a number first.

Handwriting implementation AST

The principle of

The first thing to notice is that what looks like a DOM written to a template in a.vue file is actually parsed by vue-Loader as string extraction. The principle of implementing AST is basically to iterate a string through Pointers one by one, and perform different processing according to different situations, and perform some stack operations, similar to the stack exercises above. For example, you want to convert the following code into an AST

<div>
  <h3>s</h3>
  <ul>
    <li>Qi li xiang</li>
  </ul> 
</div>
Copy the code

Conversion Target (AST)

{
  tag: "div", 
  children: [
    {
      tag: "h3", 
      children: [ { text: "Fantsea", type: 3 }], 
      type: 1,
    },
    {
      tag: "ul", 
      children: [
        {
          tag: "li", 
          children: [{ text: "Qilixiang", type: 3 }], 
          type: 1,
        }
      ], 
      type: 1,
    }
  ], 
  type: 1
}
Copy the code

We can prepare two stacks and a pointer to iterate over the template string:

• When a pointer encounters a label, it adds the label name to one stack (the label stack) and an empty array to the other stack (the array stack){tag: startTag, children: []}
• The pointer encounters a literal and changes the contents of the array at the top of the stack to a literal
• When the pointer encounters a closed label, it pushes both the label stack and the array stack out of the stack (the content of the array stack out of the stack is the content of the label out of the stack), and then combines the two elements out of the stack into the array at the top of the new stack.

The GIF is shown below

code

// index.js
import parse from './parse.js'
const templateStr = ` < div > < h3 id = "legend" class = "jay song" > s < / h3 > < ul > < li > herba blumeae < / li > < / ul > < / div > `

const ast = parse(templateStr)
console.log(ast)
Copy the code

// parse.js
import parseAttrs from './parseAttrs.js'

export default function(templateStr) {
  // Prepare a pointer
  let i = 0
  // Prepare two stacks
  {children: []} was originally added because there would be no element left in stackContent and no.children to push after the last closed tag was popped
  const stackTag = [], stackContent = [{ children: []}]// The rest of the string that begins with the pointer
  let restTemplateStr = templateStr
  // Identify the re for the start tag
  const regExpStart = /^<([a-z]+[1-6]?) (\s? [^ > > / *)

 while (i < templateStr.length - 1) {
  restTemplateStr = templateStr.substring(i)
  // The start tag is encountered
  if (regExpStart.test(restTemplateStr)) {
    const startTag = restTemplateStr.match(regExpStart)[1] / / label
    const attrsStr = restTemplateStr.match(regExpStart)[2] / / property
    // Label stack is pressed
    stackTag.push(startTag)
    // The content stack is pressed
    stackContent.push({
      tag: startTag,
      attrs: parseAttrs(attrsStr),
      type: 1.children: []
    })
    i += startTag.length + attrsStr.length  + 2 // +2 because we need < and >
  } else if (/^<\/[a-z]+[1-6]? >/.test(restTemplateStr)) { // An end tag is encountered
    const endTag = restTemplateStr.match(/^<\/([a-z]+[1-6]?) >/) [1]
    // The end label should match the top label of the label stack
    if (endTag === stackTag[stackTag.length -1]) {
      // Both stacks are stacked
      stackTag.pop()
      const popContent = stackContent.pop()
      stackContent[stackContent.length - 1].children.push(popContent)
      i += endTag.length + 3 // +3 because 
      
    } else {
      throw Error('tags' + stackTag[stackTag.length -1] + 'Not closed')}}else if (/^[^<]+<\/[a-z]+[1-6]? >/.test(restTemplateStr)) { // The content is encountered
    const wordStr = restTemplateStr.match(/^([^<]+)<\/[a-z]+[1-6]? >/) [1] // Capture the contents before the end tag  and cannot include the start tag <>
    if (!/^\s+$/.test(wordStr)) { // If the captured content is not empty
      // Assign to the element at the top of the content stack
      stackContent[stackContent.length - 1].children.push({
        text: wordStr,
        type: 3
      })
    }
    i += wordStr.length
  } else {
    i++
  }
 }
 // Because stackContent is defined with an element {children: []} added by default, we just return the first item of children
 return stackContent[0].children[0]}Copy the code

To deal with possible attributes within the tag, note that the criteria for intercepting each attribute is not simply whitespace, because attributes can have multiple values with Spaces between them, so they are judged by Spaces that are not in double quotes

// parseAttrs.js
export default function(attrsStr) {
  const attrsStrTrim = attrsStr.trim() / / to space
  if (attrsStrTrim) {
    let point = 0 / / the breakpoint
    let isYinhao = false // Whether it is in quotes
    let result = [] // Result array
    for (let index = 0; index < attrsStrTrim.length; index++) {
      if (attrsStrTrim[index] === '"') isYinhao = ! isYinhao// Intercepts a string from point to a space that is not in double quotes
      if(! isYinhao &&/\s/.test(attrsStrTrim[index])) {
        const attrs = attrsStrTrim.substring(point, index)
        result.push(attrs)
        point = index
      }
    }
    result.push(attrsStrTrim.substring(point + 1)) // The last attribute is not obtained through the for loop, so +1 is added specifically to remove the initial whitespace
    // ["id="legend"", "class="jay song""]
    result = result.map(item= > {
      // Split by equal sign
      const itemMatch = item.match(/ (+) = "(. +)" /)
      return {
        name: itemMatch[1].value: itemMatch[2]}})return result
  } else {
    return[]}}Copy the code

This concludes the main content of this sharing

One More Thing

A few additional notes on console.count() and hasOwnProperty() used in the previous code

console.count()

First, this feature is non-standard, so try not to use it in a production environment! Print the number of times count() is called, taking an optional argument label. Each call increases the count by 1 if the labels are the same, or restarts the count if they are different

hasOwnProperty()

Used to detect whether an object has a specific property of itself; Unlike the IN operator, hasOwnProperty ignores properties inherited from the prototype chain. If (cache.hasownProperty (n)) could also be written as if (n in cache).